并查集详解

前言

今天，我要来写一篇关于并查集的文章，并查集在各个OIer听来都是个很熟悉的名词，特别是正在学图论的同学们（被最小生成树当头一棒），那么，今天我就来讲讲并查集到底是何方神圣，那位高能，那么，下面进入正题！！！

并查集

并查集的基本运行原理

故事

现在请大家想象几个超级超级大的军队（百万大军或者更多），总所周知，军队分司令、军长、团长等军衔（这不是讲军衔的，不过多介绍，有兴趣者自行百度），由于这几支军队穿的军装是一样的，所以士兵见了面往往不知道是友是敌，而且由于一些特别的原因，军队也没有设置口令（容易被间谍带走），那士兵就犯难了：我该怎么样去辨别这个士兵是不是自己人呢，于是有一天，一位天才少年想出了一个办法，我们只要有一个共同的上司不就是一家人了吗，但是由于军队系统太复杂外加司令经常被调换，所以士兵军官们往往只知道自己的上级是什么，自己的上级的上级就不知道了，于是几只军队通过协商形成了这样的体系：士兵们见了别的士兵，就先向上级询问自己的司令是谁，等到上报到司令的时候司令就一挥手，说：劳资就是司令，回复去吧，于是士兵们就知道司令是谁了，这个就是并查集的基本原理，用来找自己的祖先的。

代码

int find(int x){if(pre[x]!=x)return find(pre[x]);return x;
}

合并两个并查集

故事

那么现在有两支军队握手言和了，但是由于士兵们还遵循着老传统，只要司令不一样就开战，所以这可让两军司令犯了难，想改体系已经不可能了，那该如何解决呢，于是，那位天才少年又出场了：“嗨嗨，只要你们当中的一个认另外一个为上司，那么问题不就解决了吗”，然后这位天才少年就因为让上司认大哥被活活打断了双腿，人办了，问题还是得解决的呀，上司们一合计，那行，就认你当大哥吧，于是问题又解决了。

代码

void join(int x,int y){int i=find(x),j=find(y);if(i!=j)pre[j]=i;
}

路径压缩

故事

那么这套系统运行了很多年，军队的规模也越来越大，连军长的上级的上级的上级×100都有上级了，而我们可怜的士兵依旧还得干架、找上司，士兵们发现，现在找上司要的时间越来越久了，要一天，有这时间士兵们还打什么架呢，所以士兵们通过了一些手段使得那位天才少年又又又出场了，这次，天才少年干脆建议，我们把什么师长旅长团长营长连长排长统统取消，只留下元帅和士兵，所有士兵都归一个人管，所以这位天才少年由于累惨了司令被公开处刑了，同样，还是得解决问题呀，所以上司决定，牺牲自己，让士兵们更好的干架，从此士兵们都有统一的上司了

代码

int find(int x){if(pre[x]!=x)return pre[x]=find(pre[x]);return x;
}