并查集（Union-Find-Set）簡潔而高效地處理連通分量的查詢與合并

并查集由一個整型數組和兩個函數構成

1.數組pre[]：記錄每個結點的前導結點（父節點），初始化為：pre[i]=i

2.函數unionset：合并兩個連通分量

3.函數findset：查找任意兩個點是否在同一個連通分量

可以把每個連通分量看成一個集合，該集合中包含了連通分量中的所有點。

這些點兩兩連通，而具體的連通方式無關緊要，就好比集合中的元素沒有先后順序之分，只有屬于和不屬于的區別

在圖中，每個點恰好屬于一個連通分量，對應到集合表示中，每個元素恰好屬于一個集合。

換句話說，圖的所有連通分量可以用若干個不相交集合來表示

并查集的精妙之處在于用樹來表示集合。例如，若包含點1，2，3，4，5，6的圖有3個連通分量{1，3}，{2，5，6}，{4}，

則需要用3棵樹來表示。這三棵樹的具體形態無關緊要，只要有一棵樹包含1，3兩個點，一棵樹包含2，5，6三個點，

還有一棵樹包含4這個點即可。規定每棵樹的根節點是這棵樹所對應的集合的代表元。

并查集中的路徑壓縮，在特殊情況下，這棵樹可能是一條長鏈。設鏈的最后一個節點是x，則每次執行find（x)都會遍歷整條鏈，

效率十分低下，改進方法其實很簡單。既然每棵樹表示的只是一個集合，因此樹的形態是無關精要的，并不需要在查找操作之后保持樹的形態不變，只要順便把遍歷過的節點都改成樹根的子節點，下次查找就會快很多

int pre[maxn];//pre[i]記錄i的前驅節點 int findset(int x)//查找x的根節點 {if(pre[x]==x) return x;return pre[x]=findset(pre[x]); } //合并x和y所在的連通分量 void unionset(int x,int y) {int fx=findset(x),fy=findset(y);pre[fy]=fx; }

總結

以上是生活随笔為你收集整理的并查集（Union-Find-Set）简洁而高效地处理连通分量的查询与合并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。