raghuvanshraj

765.cpp

Aug 4th, 2021
753
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  24.05.2020 02:34:11 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. void bfs(vector<vector<int>> &adj_list, int u, vector<bool> &visited) {
  10.     int n = adj_list.size();
  11.     queue<int> qu;
  12.     qu.push(u);
  13.     visited[u] = true;
  14.     while (not qu.empty()) {
  15.         int x = qu.front();
  16.         qu.pop();
  17.         for (int y : adj_list[x]) {
  18.             if (not visited[y]) {
  19.                 visited[y] = true;
  20.                 qu.push(y);
  21.             }
  22.         }
  23.     }
  24. }
  25.  
  26. int minSwapsCouples(vector<int> &arr) {
  27.     int n = arr.size();
  28.     int m = n / 2;
  29.     vector<vector<int>> adj_list(m);
  30.     for (int i = 0; i <= n - 1; i += 2) {
  31.         int u = arr[i] / 2, v = arr[i + 1] / 2;
  32.         if (u != v) {
  33.             adj_list[u].push_back(v);
  34.             adj_list[v].push_back(u);
  35.         }
  36.     }
  37.  
  38.     vector<bool> visited(m);
  39.     int count = 0;
  40.     for (int i = 0; i <= m - 1; ++i) {
  41.         if (not visited[i]) {
  42.             count++;
  43.             bfs(adj_list, i, visited);
  44.         }
  45.     }
  46.  
  47.     return m - count;
  48. }
  49.  
  50. int main(int argc, char const *argv[]) {
  51.     int n;
  52.     cin >> n;
  53.     vector<int> row(n);
  54.     for (int i = 0; i <= n - 1; ++i) {
  55.         cin >> row[i];
  56.     }
  57.  
  58.     cout << minSwapsCouples(row);
  59.  
  60.     return 0;
  61. }
RAW Paste Data