并查集(UnionFind)是一种简单高效的数据结构，主要用于解决一类连通性判断的问题。以下是经典描述：平面上最初有n个孤立的点，编号分别为1~n，随后进行m次操作，每次从中选择两个点并将它们连接起来。现在任意选出两个点，问它们是否连通？
1.初始化
设f[i]表示节点i的父节点。
void Init(int n) {
for (i = 1; i <= n; i++) f[i] = i;
}
2.合并集合
int Root(int x) {
return x == f[x] ? x : f[x] = Root(f[x]);
}
void Merge(int x, int y) {
f[Root(x)] = Root(y);
}
3.判断连通性
int IsConnected(int x, int y) {
return Root(x) == Root(y);
}
并查集的一个经典应用是Kruskal算法求最小生成树。
