文章目次
一、前言
亲爱的读者，你三十岁了吗？
以前总是讨厌父母的平庸，长大了才发现他们曾经也是怀揣着空想的少年，只是被生活磨平了棱角。现在的我们走着父母曾经走过的路，却发现也许我们还不如父母，当初他们拿着微薄的工资却养活了我，而我却照旧靠着父母几十年的积贮付了首付。
小时候总是盼着长大，如果长大后父母依旧辛苦，那我们长大尚有什么意义。
二、并查集的原理
1、“并"和"查”
- 有了深度优先搜索的底子以后，相信你对递归已经有一定的认识，那么本日让我们来认识一下并查集。
- 并查集是一种处置惩罚不相交聚集的数据结构。
它支持两种使用：
1）归并使用 m e r g e ( x , y ) merge(x, y) merge(x,y)。即归并两个原本不相交的聚集，此所谓 “并”。
2）查找使用 f i n d ( x ) find(x) find(x)。即检索某一个元素属于哪个聚集，此所谓 “查”。
- 讲个简单的故事来加深对并查集的明白，这个故事要追溯到北宋年间。话说北宋时期，朝纲败坏，奸臣当道，民不聊生。又有外侮辽军放肆南下，于是众多能人异士群起而反，各大武林门派同仇敌忾，共抗辽贼，为首的自然是中原武林第一大帮-丐帮，其帮主乃万军丛中取上将首级犹如探囊取物、泰山崩于前而面不改色的北乔峰；与其齐名的空有一腔抱负、壮志未酬的南慕容领导的慕容世家；固然也少不了天下武功的鼻祖-少林，以及一些小帮派，如逍遥派、灵鹫宫、无量剑、神农帮等等。我们将每个门派（帮派）作为一个聚集，从中选出一个代表作为这个聚集的标识，姑且认为门派（帮派）的掌门（帮主）就是这个代表。
- 作者有幸成了“抗辽同盟”的统计员，统计员只有一个工作，就是吸收一条条同门数据，然后统计共有多少个门派，好举行分派摆设。同门数据的格式为 ( x , y ) (x, y) (x,y)，体现 x x x 和 y y y 属于同一个门派，吸收到一条数据，需要对 x x x 所在的群体和 y y y 的群体举行归并，当统计完所有数据后有多少个聚集就代表多少个门派。
- 这个问题实在隐含了两个使用：
- 1）查找 a a a 和 b b b 是否已经在同一个门派；
- 2）如果两个人的门派不一致，则归并这两个人所在聚集的两堆人。分别对应了并查集的查找和归并使用。
- 如图二-1-1所示，分别体现丐帮、少林、逍遥、大理段氏四个聚集。
图二-1-1
2、质朴算法
- 接下来来讨论下并查集的质朴素现，既然是质朴素现，固然是越质朴越好啦。
- 质朴的只需要一个数组就能体现聚集，我们用 f s e t [ i ] fset fset 体现 i i i 所在的聚集编号。
质朴算法实现如下：
1）初始化每个元素一个聚集： f s e t [ i ] = i fset = i fset=i;
2）查找 x x x 属于哪个聚集，直接通过下标索引；
3）归并 x x x 和 y y y 的使用，需要判定 f s e t [ x ] fset[x] fset[x] 和 f s e t [ y ] fset[y] fset[y] 是否相等：
3.a）如果相等，则不作任何使用；
3.b）如果不相等，遍历所有满足条件 f s e t [ i ] fset fset 即是 f s e t [ x ] fset[x] fset[x] 的 i i i，设置 f s e t [ i ] = f s e t [ y ] fset = fset[y] fset=fset[y]；
- 可以把 f s e t fset fset 数组明白成哈希表，查找过程的时间复杂度为 O ( 1 ) O(1) O(1)；
- 然后，归并的时候，由于需要遍历 f s e t [ i ] fset fset，所以时间复杂度为 O ( n ) O(n) O(n) 。图二-2-1展示了质朴算法的一个例子，该数组一共记载了四个聚集，而且用每个聚集的最小数字作为该聚集的标识。
图二-2-1
[code]const int MAXN = 300010;int fset[MAXN];void init(int n) { for (int i = 1; i |
