一、模型建立
本質就是一個數組，數組的下標對應節點的編號，數組的值對應對應編號的節點的父節點。規定根節點的父節點是自己。
規定三個集合的根節點分別是1 4 6
二、并查集操作并實現
并查集主要操作：查找一個節點的父節點，判斷兩個節點是不是在一個集合，合并兩個節點所在的兩個集合。
這里的第二第三個操作是基于第一個查找父節點的，但是查找父節點的操作有一個路徑優化，所以最后再講。
1、判斷兩個節點是不是在一個集合
看看兩個節點的父節點是不是相同就行了。
bool issame(int x, int y)
{return find(x) == find(y);
}2、合并兩個節點所在的兩個集合
讓兩個節點的父節點合并，即一個父節點是另一個父節點的父節點。
void U(int x, int y)
{int root1 = find(x);int root2 = find(y);a[root1] = root2;
}3、查找一個節點的父節點
根據數組特性，只要不是數值等于下標，那就不是父節點，還需要找數值的父節點，即找當前節點的父親的父親。
int find(int x)
{if (a[x] == x)return x;return find(a[x]);
}但是如果一開始的結構是近似單支樹，那么每次查找的效率就會降低成O(N)
路徑壓縮：在遍歷到根節點之后，回溯時把回溯過程中經歷到的孩子節點的父節點全部修改成根節點，這樣就壓縮成了2層。
int find(int x)
{if (a[x] == x)return x;// 路徑壓縮：根的后代的父節點直接改成根return a[x] = find(a[x]);
}三、例題
P3367 【模板】并查集 - 洛谷
#include "bits/stdc++.h"
using namespace std;
const int N = 2 * 1e5 + 10;
int a[N];
// 查找
int find(int x)
{if (a[x] == x)return x;// 路徑壓縮：根的后代的父節點直接改成根return a[x] = find(a[x]);
}
// 合并
void U(int x, int y)
{int root1 = find(x);int root2 = find(y);a[root1] = root2;
}// 判斷
bool issame(int x, int y)
{return find(x) == find(y);
}int main()
{int n, m;cin >> n >> m;// 1.初始化所有點是單獨一個集合，根是自己for (int i = 1; i <= n; i++)a[i] = i;while (m--){int op, x, y;cin >> op >> x >> y;if (op == 1)U(x, y);elseissame(x, y) == true ? cout << "Y" << endl : cout << "N" << endl;}return 0;
}
)
)
)
