天天看點

并查集—解密幫派

警察想查清楚有幾個幫派,搜集到了一些線索:

現在有10個強盜;

1号強盜與2号強盜是同夥;

3号強盜與4号強盜是同夥;

5号強盜與2号強盜是同夥;

4号強盜與6号強盜是同夥;

2号強盜與6号強盜是同夥;

8号強盜與7号強盜是同夥;

9号強盜與7号強盜是同夥;

1号強盜與6号強盜是同夥;

2号強盜與4号強盜是同夥;

強盜同夥的同夥也是同夥,請問一共有多少個獨立的幫派?

基本思路:

1.一維數組f,表示10個強盜,值存儲每個強盜的boss是誰。

2.初始化,開始boss都是自己,f[i]=i。

并查集—解密幫派

3.合并同夥,“靠左”法則,“1号強盜與2号強盜是同夥”,2号的boss變成了1号,f[2]=1。

并查集—解密幫派

。。。。。。

第三條線索:“5号強盜與2号強盜是同夥”,2号的boss目前是1号,“擒賊先擒王”,那麼讓1号的boss直接變為5号,即f[1]=5,f[2]=5。

。。。。。。

最終結果:

并查集—解密幫派

如果f[i]=i,就表示此人是一個幫派的最高上司人,有多少個獨立的團夥,等于看最終結果中有多少個f[i]=i。

并查集:

通過一個一維數組來實作,其本質是維護一個森林。剛開始的時候,森林的每個點都是孤立的,也可以了解為每個點就是一棵隻有一個節點的樹,之後通過一些條件,将這些樹合并成一棵大樹。

合并過程中,“靠左”法則和“擒賊先擒王”原則。

并查集—解密幫派
并查集—解密幫派
并查集—解密幫派

輸入資料:

第一行n,m,分别表示強盜人數,和線索條數,接下來m行有兩個數a,b,表示a和 b是同夥。

并查集—解密幫派

運作結果:

并查集—解密幫派

并查集也稱為不相交集資料結構。