带路径压缩的并查集模板：
class UnionFind{
public:
vector<int>father;
UnionFind(int num){//num表示元素的个数
for(int i = 0; i < num; i++){
father.push_back(i);//箭头指向自己
}
}
int Find(int n){
//递归
if(father[n] == n)
return n;
father[n] = Find(father[n]);//路径压缩版本
return father[n];
}
void Union(int a, int b){
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
}
};
另外并查集复杂度平均下来每次查询和合并的复杂度都是常数的（阿克曼函数）。
证明的话比较复杂，有兴趣的同学可以看Tarjan R E, Van Leeuwen J. Worst-case analysis of set union algorithms[J]. Journal of the ACM (JACM), 1984, 31(2): 245-281.这个论文哈（我也不会
这个模板union的时候如果是搜索，第一个和第二个换人也太频繁了，能不能先加个判断；
void Union(int a, int b){
if(father[a]==b||father[b]==a)return;
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
}
不会换人呀，如果father[a]==b说明a和b是同一个集合里的，那么fa与fb相等，祖宗节点的father就是指向自己，所以实际上各个节点的father指针都没有做任何改变呀
撒拉嘿呦⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄
♪(^∇^*)
万一是坏的数据结构查询起来就复杂，建议加上权值
啥叫坏的数据结构？另外带权并查集是要根据题意来确定每个节点的权值吧，不太明白放在模板里怎么写
就是生成的树深度很深，不利于每次的查找，要是加权的话，引入一个数组确保每次都是小的连接到大的上就好了
你说的是按大小合并或者按秩合并吧，这个在没有路径压缩的时候确实是一个优化方式。
不过这个模板已经做了路径压缩优化了，树的深度会在Find执行的时候被自动减少，所以不会有性能问题。
Mystery说的好有道理
这一题union那一个函数只是改变了大哥的指向，并没有将剩下的成员都指向合并后的大哥，改变所有成员的指向是在find函数中做的，可以这么理解吧。
find时，将涉及到的点顺带进行路径压缩
因为是递归的过程，所以会将查询的时候所有经过的元素的指向都改变，可以自己模拟一下就明白了。
题目是leetcode547、200、684
题解
https://www.acwing.com/solution/LeetCode/content/2012/，https://www.acwing.com/solution/LeetCode/content/2013/，https://www.acwing.com/solution/LeetCode/content/2014/
赞