1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27

#include <vector>
using namespace std;

class UFDS {
private: int num_sets; vector<int> p, rank, size;
public:
	UFDS(int N) {
		num_sets = N;
		p.assign(N, 0);
		for (int i = 0; i < N; i++) p[i] = i;
		rank.assign(N, 0);
		size.assign(N, 1);
	}
	int find_set(int i) { return (p[i] == i) ? i : (p[i] = find_set(p[i])); }
	bool same_set(int i, int j) { return find_set(i) == find_set(j); }
	int sets() { return num_sets; }
	int size_set(int i) { return size[find_set(i)]; }
	void union_set(int i, int j) {
		if (same_set(i, j)) return;
		int x = find_set(i), y = find_set(j);
		if (rank[x] > rank[y]) swap(x, y);
		p[x] = y;
		if (rank[x] == rank[y]) rank[y]++;
		size[y] += size[x];
		--num_sets;
	}
};