Union Find木(ATC B問題)

ABC065 D - Built?を解く→(((ง ･ө･ )ว？ﾜｶﾗﾝﾁﾝ→解説「最小全域木はご存知ですよね」→*1cout << "Yes" << endl;

else cout << "No" << endl;

}

}

}

*1:;ﾟДﾟ)ｵﾚｼﾗﾅｲｼﾗﾅｲ→最小全域木の解説「閉路の判定にはUnion-Find木を用いると良いです」→Union-Find木って😩💭ﾅﾝｬ‥‥｡

というわけで、Union-Find木から勉強します
問題
以下ネタバレ注意

1. const int MAX = 100010;
2. int par[MAX];//親
3. int Rank[MAX];//木の深さ
4.  
5. //n要素で初期化
6. void init(int n) {
7. REP(i, n) {
8. par[i] = i;
9. Rank[i] = 0;
10. }
11. }
12.  
13. //木の根を求める
14. int find(int x) {
15. if (par[x] == x) {
16. return x;
17. }
18. else {
19. return par[x] = find(par[x]);//経路圧縮(根に直接つなぎなおす)もしつつ
20. }
21. }
22.  
23. //xとyの属する集合を併合
24. void unite(int x, int y) {
25. x = find(x);
26. y = find(y);
27. if (x == y)return;
28. //低いほうを高いほうにつなげる(効率化)
29. if (Rank[x] < Rank[y]) {
30. par[x] = y;
31. }
32. else {
33. par[y] = x;
34. if (Rank[x] == Rank[y])Rank[x]++;
35. }
36. }
37.  
38. //xとyが同じ集合に属するか否か
39. bool same(int x, int y) {
40. return find(x) == find(y);
41. }
42.  
43.  
44. int N, Q;
45. int P[200010], A[200010], B[200010];
46. int main() {
47. cin >> N >> Q;
48. init(N);
49. REP(i, Q) {
50. cin >> P[i] >> A[i] >> B[i];
51. }
52. REP(i, Q) {
53. //連結クエリ
54. if (P[i] == 0) {
55. unite(A[i], B[i]);
56. }
57. //判定クエリ
58. if (P[i] == 1) {
59. if (same(A[i], B[i]