一.初始版
并查集，顾名思义，就是“合并查找集合”，所以我们先要进行查找再合并。不过，在此之前，还有一个步骤——初始化。
1.初始化
inline void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; } }
并查集是树的应用。而初始时，每个量的根都是它本身，所以就是这样做。
2.查找
int find(int x) { if(fa[x]==x) return x; else { return find(fa[x]); } }
因为并查集是一种树的应用，因此可以用递归找它的根。
3.合并
inline void merge(int i,int j) { int x=find(i),y=find(j); fa[x]=y; }
合并是通过寻找两数最大的根，并将其中一数转化为与其合并的另一数，即为变化根。
4.组合
#include<bits/stdc++.h> using namespace std; int fa[20005]; inline void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; rank[i]=1; } } int find(int x) { if(fa[x]==x) return x; else { fa[x]=find(fa[x]); return fa[x]; } } inline void merge(int i,int j) { int x=find(i),y=find(j); if(rank[x]>=rank[y]) { fa[y]=x; } else fa[x]=y; } int main() { return 0; }
将它们组合起来便是这样，但这些在main函数中可能会被调用许多次，因此必须优化，否则必定超时。这是，路径优化就有作用了！
二.路径优化版
通过观察发现，寻找那里重复了不少操作，因为fa[i]存的只是它上层的根，而不是最大的根，这样每次都要寻找，耗费不小时间。这时我想到，可以把i最大的根（递归结果）更新到fa[i]，再返回fa[i]，就是下面那样：
int find(int x) { if(fa[x]==x) return x; else { fa[x]=find(fa[x]); return fa[x]; } }
不过，这样也可能会超时……
三.按迭合并
很明显，大合小比小合大的深度要大，因此我们选择小合大，具体操作如下：
inline void merge(int i,int j) { int x=find(i),y=find(j); if(rank[x]>=rank[y]) { fa[y]=x; } else fa[x]=y; }
建立一个数组rank[i]，执行init函数时顺便把它们标为1，之后的操作在上面。（你不会看不懂吧？！）
四.完整并查集通用模板
#include<bits/stdc++.h> using namespace std; int fa[20005],rank[20005]; inline void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; rank[i]=1; } } int find(int x) { if(fa[x]==x) return x; else { fa[x]=find(fa[x]); return fa[x]; } } inline void merge(int i,int j) { int x=find(i),y=find(j); if(rank[x]>=rank[y]) { fa[y]=x; } else fa[x]=y; } int main() { return 0； }
为了是你们提升阅读代码的能力，我就不写注释了。（实际因为太懒）
