并查集

顾名思义，并查集有三个用处

并，即合并两个集合

查，查询该元素所在的集合

集，就指集合

现在来说一说并查集的基本操作：

- 初始化

首先，最开始的时候，我们假设所有的集合都只有一个元素，即只有自己（自己是自己的爸爸。。。）。所以简单初始化：

for(int i=1;i<=num;i++){        father[i]=i;        }

那么很好理解，如果你们的祖先一定是一个人，那你们是一家人对吧，所以 有公共祖先的两个元素在同一集合内

现在，我们可以对这num个集合操作了

- 认亲

我们把并查集的名字设为father，那么合并集合是不是就是认亲啊 = =；

好吧再通俗点叫认祖宗

a：诶我们家没钱了QAQ

b：没事我们家可以收养你

a：我还有一家人（数不清的爸爸们QAQ）挨饿啊

b：没事没事，我们家有的是钱，让你祖宗认我们家祖宗是爸爸，我们就是一家人了呗QVQ

a：是哦！！！！！

好吧，有点扯，不过就是这么回事（findfather函数参见下面的找爸爸）

void Union(int a,int b){        int faA=findfather(a);//找a祖宗        int faB=findfather(b);//找b祖宗        if(faA!=faB){            father[faA]=faB;//认爸爸            }        }

- 找爸爸

顾名思义，就是找你的爸爸的爸爸的爸爸（递归一波：））

a：我看看。。。诶我祖宗是G诶

b：卧槽我祖宗也是G

a+b：诶哟一家人

int father[maxn];    int findfather(int x){        while(x!=father[x]){//一直找到祖先为止            x=father[x];            }        return x;        }

实现的是并查集中查的作用，很好理解，就是像一条线一样，顺着线的源头一直找下去，直到找到一个自己的源头是自己元素，那么那个源头就是最大的爸爸了（就你那个老不死祖先QwQ）

但这种找发也有不足：如果G是a的 55555 代祖宗，那么a不是要找 55555 次才能找到？那不得累死QAQ

这样的一条链大大降低了找爸爸的效率

所以我们需要对其进行优化，不妨这样：

每次找到（最大）祖先，就替换自己的爸爸

理解如下，father[i]的值现在不代表i的爸爸了，而代表i的最大祖先

a：祖先？我看看

（打开族谱，发现只有一页：你的祖先是G）

我的祖先是G

b:哦哦，我看看我的

（然后翻了55555页，每一页都是 { x的爸爸是Y } ，最后终于找到了father[G] = G）

f*ck，终于翻到了，我祖先是G

一对比，就发现路径压缩的好处了

具体代码实现：

int findfather(int v){        if(father[v]==v){            return v;//找到祖宗了= =            }        else{            int F=findfather(father[v]);//记住你祖宗            father[v]=F;//修改一下祖宗            return F;//一层一层回去            }        }