警察想查清楚有幾個幫派,搜集到了一些線索:
現在有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。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIyVGduV2QvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2LcNnRXpVeo1GZ1I1MkZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39jNwkTM1QDNxIDNwIDM1EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
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是同夥。
運作結果:
并查集也稱為不相交集資料結構。