Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector<int> parent;
- vector<int> qty;
- void resize (int n)
- {
- parent.resize(n);
- qty.resize(n);
- }
- void make_set(int x)
- {
- parent[x] = x;
- qty[x] = 1;
- }
- int find_set(int x)
- {
- if (parent[x]==x)
- {
- return x;
- }
- return parent[x] = find_set(parent[x]);
- }
- void do_union_set (int root, int v)
- {
- parent[v] = root;
- qty[root] += qty[v];
- }
- bool union_set (int x, int y)
- {
- int rx = find_set(x), ry = find_set(y);
- if (rx == ry)
- {
- return false;
- }
- if (qty[rx] < qty[ry])
- {
- do_union_set(ry, rx);
- }
- else
- {
- do_union_set(rx, ry);
- }
- return true;
- }
- int main()
- {
- int n, m;
- cin >>n >>m;
- resize(n + 1);
- for (int i = 1; i <= n; i++)
- {
- make_set(i);
- }
- //{{1},{2},....,{n}}
- for (int i = 1; i <= m; i++)
- {
- int ki;
- cin >>ki;
- int prev;
- if (ki >= 1)
- {
- cin >> prev;
- for (int j = 2; j <= ki; j++)
- {
- int curr;
- cin >>curr;
- union_set(prev, curr);
- prev = curr;
- }
- }
- }
- for (int i = 1; i <= n; i++)
- {
- cout <<qty[find_set(i)] <<" ";
- }
- cout <<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement