Niloy007

Find Connected Component in Disjoint Set

May 7th, 2021
683
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define N_VERTICES 1000
  4.  
  5. class DisjointSet {
  6.     int p[N_VERTICES];
  7.  
  8.   public:
  9.     void make_set(int x) {
  10.         p[x] = x;
  11.     }
  12.  
  13.     int find_set(int x) {
  14.         while (x != p[x]) {
  15.             x = p[x];
  16.         }
  17.         return x;
  18.     }
  19.  
  20.     void union_set(int x, int y) {
  21.         int a = find_set(x);
  22.         int b = find_set(y);
  23.         p[a] = b;
  24.     }
  25.  
  26.     bool same_set(int x, int y) {
  27.         if (find_set(x) == find_set(y)) {
  28.             return true;
  29.         }
  30.         return false;
  31.     }
  32. };
  33.  
  34.  
  35. class Graph {
  36.   public:
  37.     int mat[N_VERTICES][N_VERTICES];
  38.  
  39.     void init_graph() {
  40.         for (int i = 0; i < N_VERTICES; i++) {
  41.             for (int j = 0; j < N_VERTICES; j++) {
  42.                 mat[i][j] = 0;
  43.             }
  44.         }
  45.     }
  46.  
  47.     void add_edge(int u, int v) {
  48.         mat[u][v] = 1;
  49.         mat[v][u] = 1;
  50.     }
  51.  
  52.     DisjointSet connected_component(int n) {
  53.         DisjointSet S;
  54.         for (int i = 0; i < n; i++) {
  55.             S.make_set(i);
  56.         }
  57.  
  58.         for (int i = 0; i < n; i++) {
  59.             for (int j = 0; j < n; j++) {
  60.                 if (mat[i][j]) {
  61.                     if (S.find_set(i) != S.find_set(j)) {
  62.                         S.union_set(i, j);
  63.                     }
  64.                 }
  65.             }
  66.         }
  67.         return S;
  68.     }
  69. };
  70.  
  71.  
  72. int main() {
  73.     Graph G;
  74.     G.init_graph();
  75.  
  76.     int v, e;
  77.     cin >> v >> e;
  78.  
  79.     for (int i = 0; i < e; i++) {
  80.         int u, v;
  81.         cin >> u >> v;
  82.         G.add_edge(u, v);
  83.     }
  84.  
  85.     DisjointSet ds = G.connected_component(v);
  86.  
  87.     set<int> st;
  88.     for (int i = 0; i < v; i++) {
  89.         st.insert(ds.find_set(i));
  90.     }
  91.     cout << st.size() << endl;
  92. }
  93.  
  94.  
  95. /*
  96. Input:
  97.  
  98. 4
  99. 3
  100. 0 1
  101. 2 3
  102. 3 2
  103.  
  104. 3
  105. 3
  106. 0 1
  107. 1 2
  108. 2 0
  109.  
  110. */
  111.  
  112.  
RAW Paste Data