文章目次
一、前言
亲爱的读者,你三十岁了吗?
以前总是讨厌父母的平庸,长大了才发现他们曾经也是怀揣着空想的少年,只是被生活磨平了棱角。现在的我们走着父母曾经走过的路,却发现也许我们还不如父母,当初他们拿着微薄的工资却养活了我,而我却照旧靠着父母几十年的积贮付了首付。
小时候总是盼着长大,如果长大后父母依旧辛苦,那我们长大尚有什么意义。
二、并查集的原理
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 |