Advertisement
JouJoy

W

Dec 12th, 2021
725
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector<int> parent;
  7. vector<int> qty;
  8.  
  9. void resize (int n)
  10. {
  11.     parent.resize(n);
  12.     qty.resize(n);
  13. }
  14.  
  15. void make_set(int x)
  16. {
  17.     parent[x] = x;
  18.     qty[x] = 1;
  19. }
  20.  
  21. int find_set(int x)
  22. {
  23.     if (parent[x]==x)
  24.     {
  25.         return x;
  26.     }
  27.     return parent[x] = find_set(parent[x]);
  28. }
  29.  
  30. void do_union_set (int root, int v)
  31. {
  32.     parent[v] = root;
  33.     qty[root] += qty[v];
  34. }
  35.  
  36. bool union_set (int x, int y)
  37. {
  38.     int rx = find_set(x), ry = find_set(y);
  39.    
  40.     if (rx == ry)
  41.     {
  42.         return false;
  43.     }
  44.    
  45.     if (qty[rx] < qty[ry])
  46.     {
  47.         do_union_set(ry, rx);
  48.     }
  49.     else
  50.     {
  51.         do_union_set(rx, ry);
  52.     }
  53.     return true;
  54. }
  55.  
  56. int main()
  57. {
  58.     int n, m;
  59.     cin >>n >>m;
  60.    
  61.     resize(n + 1);
  62.     for (int i = 1; i <= n; i++)
  63.     {
  64.         make_set(i);
  65.     }
  66.     //{{1},{2},....,{n}}
  67.    
  68.     for (int i = 1; i <= m; i++)
  69.     {
  70.         int ki;
  71.         cin >>ki;
  72.         int prev;
  73.         if (ki >= 1)
  74.         {
  75.             cin >> prev;
  76.             for (int j = 2; j <= ki; j++)
  77.             {
  78.                 int curr;
  79.                 cin >>curr;
  80.                 union_set(prev, curr);
  81.                 prev = curr;
  82.             }
  83.         }
  84.     }
  85.    
  86.     for (int i = 1; i <= n; i++)
  87.     {
  88.         cout <<qty[find_set(i)] <<" ";
  89.     }
  90.     cout <<endl;
  91.  
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement