參考
1. 舉例分析
1.1. 案例說明
快過年了，犯罪分子們也開始為年終獎“奮斗”了沙咏，小哼的家鄉(xiāng)出現(xiàn)了多次搶劫事件。由于強盜人數(shù)過于龐大，作案頻繁扒接，警方想查清楚到底有幾個犯罪團伙實在是太不容易了，不過警察叔叔還是搜集到了一些線索们衙，需要咱們幫忙分析一下钾怔。
現(xiàn)在有11個強盜。
1號強盜與2號強盜是同伙砍艾。
3號強盜與4號強盜是同伙。
5號強盜與2號強盜是同伙巍举。
4號強盜與6號強盜是同伙脆荷。
2號強盜與6號強盜是同伙。
7號強盜與11號強盜是同伙懊悯。
8號強盜與7號強盜是同伙蜓谋。
9號強盜與7號強盜是同伙。
9號強盜與11號強盜是同伙炭分。
1號強盜與6號強盜是同伙桃焕。
有一點需要注意：強盜同伙的同伙也是同伙。你能幫助警方查出有多少個獨立的犯罪團伙嗎捧毛？
1.2. 步進分析
要想解決這個問題观堂，首先我們假設(shè)這11個強盜相互是不認識的让网，他們各自為政，每個人都是首領(lǐng)师痕，他們只聽從自己的溃睹。之后我們將通過警方提供的線索，一步步地來“合并同伙”胰坟。
第一步：我們申請一個一維數(shù)組f因篇，我們用f[1]f[11]分別存儲111號強盜中每個強盜的首領(lǐng)“BOSS”是誰。
第二步：初始化笔横。根據(jù)我們之前的約定竞滓，這11個強盜最開始是各自為政的，每個強盜的BOSS就是自己吹缔∩逃樱“1號強盜”的BOSS就是“1號強盜”自己，因此f[1]的值為1涛菠。以此類推莉御，“11號強盜”的BOSS是“11號強盜”，即f[11]的值為11俗冻。請注意礁叔，這是很重要的一步。
第三步：開始“合并同伙”琅关，即如果發(fā)現(xiàn)目前兩個強盜是同伙，則這兩個強盜是同一個犯罪團伙〖ケ危現(xiàn)在有一個問題：合并之后誰才是這個犯罪團伙的BOSS呢涣易？
例如警方得到的第1條線索是“1號強盜與2號強盜是同伙”∫鄙。“1號強盜”和“2號強盜”原來的BOSS都是自己新症，如今發(fā)現(xiàn)“1號強盜”和“2號強盜”其實是同一個犯罪團伙，那么究竟是讓“1號強盜”變成“2號強盜”的BOSS响禽，還是讓“2號強盜”變成“1號強盜”的BOSS呢徒爹？一個犯罪團伙只能有一個首領(lǐng)。其實無所謂芋类，都可以隆嗅。我們這里假定左邊的強盜更厲害一些，給這個規(guī)定起個名字叫作“靠左”法則侯繁。也就是說“2號強盜”的BOSS將變成“1號強盜”胖喳。因此我們將f[2]中的數(shù)改為1，表明“2號強盜”歸順了“1號強盜”贮竟。其實準確地說應(yīng)該是原本歸順“2號強盜”的所有人都歸順了“1號強盜”才對丽焊，只不過此時“2號強盜”只孤身一人较剃，因此只需要將f[2]的值改為1。不要著急粹懒，繼續(xù)往后面看重付，你就知道我為什么這樣說了，如下凫乖。
警方得到的第2條線索是“3號強盜與4號強盜是同伙”确垫，說明“3號強盜”和“4號強盜”也是同一個犯罪團伙。根據(jù)“靠左”原則“4號強盜”歸順了“3號強盜”帽芽，所以f[4]中的值要改為3删掀，原理和剛才處理第1條線索是一樣的，如下导街。
警方得到的第3條線索是“5號強盜”與“2號強盜”是同伙披泪。f[5]的值是5，說明“5號強盜”的BOSS仍然是自己搬瑰。f[2]的值是1款票，說明“2號強盜”的BOSS是“1號強盜”。根據(jù)“靠左”法則泽论，右邊的強盜必須歸順于左邊的強盜艾少。此時你可能會將f[2]的值改為5。注意啦翼悴！此時如果你將f[2]的值改為5缚够，就是說讓“2號強盜”歸順“5號強盜”。那“1號強盜”可就不干了鹦赎，你憑什么搶我的人谍椅？他非跟你干一架不可。這樣會讓“2號強盜”很難選擇古话，我究竟歸順誰好呢雏吭？
現(xiàn)在我來給你支個招，嘿嘿( _ )古語云“擒賊先擒王”陪踩。你直接找“2號強盜”的BOSS“1號強盜”談杖们，讓其歸順“5號強盜”就OK了，也就是將f[1]的值改為5〔不伲現(xiàn)在“2號強盜”的BOSS是“1號強盜”胀莹，而“1號強盜”的BOSS變成了“5號強盜”基跑，即“1號強盜”帶領(lǐng)手下“2號強盜”歸順了“5號強盜”婚温，這樣所有的關(guān)系信息就都保留下來了。如下媳否。
警方得到的第4條線索是“4號強盜”與“6號強盜”是同伙栅螟。f[4]的值是3荆秦，f[6]的值是6。根據(jù)“靠左”原則力图，讓“6號強盜”加入“3號犯罪團伙”步绸。我們需要將f[6]的值改為3。原理和處理第1條和第2條線索相同吃媒。
警方得到的第5條線索是“2號強盜”與“6號強盜”是同伙瓤介。f[2]的值是1，f[1]的值是5赘那，即“2號強盜”的大BOSS（首領(lǐng)）是“5號強盜”刑桑。f[6]的值是3，即“6號強盜”的BOSS是“3號強盜”募舟。根據(jù)“靠左”原則和“擒賊先擒王”原則祠斧，讓“6號強盜”的BOSS“3號強盜”歸順“2號強盜”的大BOSS（首領(lǐng)）“5號強盜”。因此我們需要將f[3]的值改為5拱礁，即讓“3號強盜”帶領(lǐng)其手下歸順“5號強盜”琢锋。
需要特別注意的是，此時呢灶，“5號強盜”團伙內(nèi)部發(fā)生了一些變動吴超。我們在尋找“2號強盜”的大BOSS（首領(lǐng)）是誰時，順帶將f[2]從1改成了5填抬，也就是說現(xiàn)在“2號強盜”也變成大BOSS（首領(lǐng)）“5號強盜”的直屬手下了烛芬。
這就是強盜團伙的江湖規(guī)矩，誰能找到自己幫派的大BOSS（首領(lǐng)）飒责，誰就會被大BOSS（首領(lǐng)）提拔赘娄，升職加薪，成為大BOSS（首領(lǐng)）的直屬手下宏蛉。這種扁平化管理的方式可以有效地提高強盜團伙找大BOSS的效率遣臼，在“并查集”算法中有一個專門的術(shù)語，叫作“路徑壓縮”拾并，具體代碼在后面展示揍堰。
細心的同學會問了，剛才不是說如果直接把f[2]改成5嗅义，“2號強盜”和“1號強盜”之間的關(guān)系就斷了嗎屏歹？此一時，彼一時之碗。在得到第3條線索的時候蝙眶，那時候“1號強盜”和“5號強盜”的關(guān)系還沒有建立起來，如果把f[2]改為5褪那，“2號強盜”想要找 “1號強盜”就找不到了幽纷。但到了第5條線索的時候式塌，“2號強盜”和“1號強盜”已經(jīng)都在大BOSS（首領(lǐng)）“5號強盜”手下工作了，這時候?qū)[2]改為5友浸，“2號強盜”想找大BOSS（首領(lǐng)）“5號強盜”變得更加方便峰尝，而“1號強盜”和“2號強盜”之間的關(guān)系也沒有丟失，因此整體上效率變得更高了收恢。
警方得到的第6條線索是“7號強盜”與“11號強盜”是同伙武学。f[11]的值是11，f[7]的值是7伦意。根據(jù)“靠左”原則劳淆，讓“11號強盜”歸順“7號強盜”。我們需要將f[11]的值改為7默赂。
警方得到的第7條線索是“8號強盜”與“7號強盜”是同伙沛鸵。f[8]的值是8，f[7]的值是7缆八。根據(jù)“靠左”原則曲掰，讓“7號強盜”歸順“8號強盜”。我們需要將f[7]的值改為8奈辰。
警方得到的第8條線索是“9號強盜”與“7號強盜”是同伙栏妖。f[9]的值是9，f[7]的值是8奖恰。根據(jù)“靠左”原則和“擒賊先擒王”原則吊趾，我們需要將f[8]的值改為9。
警方得到的第9條線索是“9號強盜”與“11號強盜”是同伙瑟啃。f[9]的值是9论泛，f[11]的值是7。什么蛹屿？他們竟然不在同一個犯罪團伙中屁奏？這貌似不對吧，通過上圖可以很顯然地看出來“11號強盜”和“9號強盜”都在同一個犯罪團伙中错负。不過“11號強盜”并不直屬于大BOSS（首領(lǐng)）“9號強盜”坟瓢，而是歸順在“7號強盜”的手下。現(xiàn)在來看看“7號強盜”又歸順了誰呢犹撒？我們發(fā)現(xiàn)f[7]=8折联，也就是說“7號強盜”歸順了“8號強盜”。而f[8]=9识颊，也就是說“8號強盜”歸順了“9號強盜”诚镰。我們再來看看“9號強盜”有沒有歸順于別的人。發(fā)現(xiàn)f[9]的值還是9，太牛了怕享！說明“9號強盜”的BOSS仍然是自己，他就是所在團伙的大BOSS（首領(lǐng)）镰踏。
我們剛才模擬的過程其實就是遞歸的過程函筋。從“11號強盜”順藤摸瓜一直找到他所在團伙的大BOSS（首領(lǐng)）“9號強盜”。剛才說了奠伪，強盜團伙的江湖規(guī)矩是跌帐，誰能找到自己幫派的大BOSS（首領(lǐng)），就會被提拔為首領(lǐng)的直屬手下绊率。經(jīng)過這一次“路徑壓縮”谨敛，一路上“11號強盜”“7號強盜”和“8號強盜”，都找到了自己的大BOSS“9號強盜”滤否。下次再問他們的BOSS是誰的時候脸狸，他們就能馬上回答出是“9號強盜”啦。
警方得到的最后一條線索是“1號強盜”與“6號強盜”是同伙藐俺。這又是一次“路徑壓縮”的過程炊甲。f[1]是5，“1號強盜”的BOSS是“5號強盜”欲芹。f[6]是3卿啡，“6號強盜”的BOSS是“3號強盜”。f[3]是5菱父，“3號強盜”的BOSS是“5號強盜”颈娜。說明“6號強盜”和“1號強盜”是在一個團伙中的，但他現(xiàn)在并不是直接跟著團伙的大BOSS（首領(lǐng)）“5號強盜”浙宜，而是跟著“3號強盜”官辽。而經(jīng)過這次“路徑壓縮”，他的BOSS就改成了“5號強盜”粟瞬。但是注意野崇，這一次的“路徑壓縮”只發(fā)生在“6號強盜”“3號強盜”“5號強盜”這條路徑上，團伙中的“4號強盜”不在被壓縮的路徑上亩钟，所以他的BOSS暫時不會改變乓梨，還是“3號強盜”。
好了清酥，所有的線索分析完畢扶镀，那么究竟有多少個犯罪團伙呢？我想你從上面的圖中一眼就可以看出來了焰轻，一共有3個犯罪團伙臭觉，分別是5號犯罪團伙（由5、1、2蝠筑、3狞膘、4、6號強盜組成）什乙，9號犯罪團伙（由9挽封、8、7臣镣、11號強盜組成）以及10號犯罪團伙（只有10號強盜一個人）辅愿。從下面這張圖就可以清晰地看出，如果f[i]=i忆某，就表示此人是一個犯罪團伙的最高領(lǐng)導人点待，有多少個最高領(lǐng)導人就是有多少個“獨立的犯罪團伙”。最后數(shù)組中f[5]=5弃舒、f[9]=9癞埠、f[10]=10，因此有3個獨立的犯罪團伙聋呢。
我們剛才模擬的過程其實就是并查集的算法燕差。并查集通過一個一維數(shù)組來實現(xiàn)，其本質(zhì)是維護一個森林坝冕。剛開始的時候徒探，森林的每個點都是孤立的，也可以理解為每個點就是一棵只有一個結(jié)點的樹喂窟，之后通過一些條件测暗，逐漸將這些樹合并成一棵大樹。其實合并的過程就是“認爹”的過程磨澡。在“認爹”的過程中碗啄，要遵守“靠左”原則和“擒賊先擒王”原則。在每次判斷兩個結(jié)點是否已經(jīng)在同一棵樹中的時候（一棵樹其實就是一個集合）稳摄，也要注意必須求其根源稚字，中間父親結(jié)點（“小BOSS”）是不能說明問題的，必須找到其祖宗（樹的根結(jié)點）厦酬，判斷兩個結(jié)點的祖宗是否是同一個根結(jié)點才行胆描。下面我將“解密犯罪團伙”這個問題模型化，并給出代碼和注釋：
#include <stdio.h>
int f[1001]={0},n,m,sum=0;
//這里是初始化仗阅，非常地重要昌讲，數(shù)組里面存的是自己數(shù)組下標的編號就好了。
void init()
{
int i;
for(i=1;i<=n;i++)
f[i]=i;
return;
}
//這是找爹的遞歸函數(shù)减噪，不停地去找爹短绸，直到找到祖宗為止车吹，其實就是去找犯罪團伙的最高領(lǐng)導人，
//“擒賊先擒王”原則醋闭。
int getf(int v)
{
if(f[v]==v)
return v;
else
{
//這里是路徑壓縮窄驹，每次在函數(shù)返回的時候，順帶把路上遇到的人的“BOSS”改為最后找
//到的祖宗編號证逻，也就是犯罪團伙的最高領(lǐng)導人編號乐埠。這樣可以提高今后找到犯罪團伙的
//最高領(lǐng)導人（其實就是樹的祖先）的速度。
f[v]=getf(f[v]);//這里進行了路徑壓縮
return f[v];
}
}
//這里是合并兩子集合的函數(shù)
void merge(int v,int u)
{
int t1,t2;//t1瑟曲、t2分別為v和u的大BOSS（首領(lǐng)），每次雙方的會談都必須是各自最高領(lǐng)導人才行
t1=getf(v);
t2=getf(u);
if( t1!=t2 ) //判斷兩個結(jié)點是否在同一個集合中豪治，即是否為同一個祖先洞拨。
{
f[t2]=t1;
//“靠左”原則，左邊變成右邊的BOSS负拟。即把右邊的集合烦衣，作為左邊集合的子集合。
}
return;
}
//請從此處開始閱讀程序掩浙，從主函數(shù)開始閱讀程序是一個好習慣花吟。
int main()
{
int i,x,y;
scanf("%d %d",&n,&m);
init(); //初始化是必須的
for(i=1;i<=m;i++)
{
//開始合并犯罪團伙
scanf("%d %d",&x,&y);
merge(x,y);
}
//最后掃描有多少個獨立的犯罪團伙
for(i=1;i<=n;i++)
{
if(f[i]==i)
sum++;
}
printf("%d\n",sum);
getchar();getchar();
return 0;
}
可以輸入以下數(shù)據(jù)進行驗證。第一行n m厨姚，n表示強盜的人數(shù)衅澈，m表示警方搜集到的m條線索。接下來的m行每一行有兩個數(shù)a和b谬墙，表示強盜a和強盜b是同伙今布。
11 10
1 2
3 4
5 2
4 6
2 6
7 11
8 7
9 7
9 11
1 6
運行結(jié)果是：
3
2. 結(jié)語
并查集也稱為不相交集數(shù)據(jù)結(jié)構(gòu)。此算法的發(fā)展經(jīng)歷了十多年拭抬，研究它的人也很多部默，其中Robert E. Tarjan做出了很大的貢獻。在此之前John E. Hopcroft和Jeffrey D. Ullman也進行了大量的分析造虎。你是不是又感覺Robert E. Tarjan和John E. Hopcroft很熟悉傅蹂？沒錯，就是發(fā)明了深度優(yōu)先搜索的兩個人——1986年的圖靈獎得主算凿。你看牛人們從來都不閑著的份蝴。他們到處交流，尋找合作伙伴氓轰，一起改變世界搞乏。
