反饋

並查集

並查集，在一些有N個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然後按一定順序將屬於同一組的元素所在的集合合併，其間要反覆查找一個元素在哪個集合中。這一類問題反覆出現在信息學的國際國內賽題中。其特點是看似並不複雜，但數據量極大，若用正常的數據結構來描述的話，往往在空間上過大，計算機無法承受；即使在空間上勉強通過，運行的時間複雜度也極高，根本就不可能在比賽規定的運行時間（1～3秒）內計算出試題需要的結果，只能用並查集來描述。

並查集是一種樹型的數據結構，用於處理一些不相交集合（disjoint sets）的合併及查詢問題。常常在使用中以森林來表示。

中文名: 並查集
外文名: union-find disjoint sets
DSU

所屬學科: 信息學
 計算機科學
用途: 計算機編碼

並查集主要操作

並查集初始化

把每個點所在集合初始化為其自身。

通常來説，這個步驟在每次使用該數據結構時只需要執行一次，無論何種實現方式，時間複雜度均為

。

並查集查找

查找元素所在的集合，即根節點。

並查集合併

將兩個元素所在的集合合併為一個集合。

通常來説，合併之前，應先判斷兩個元素是否屬於同一集合，這可用上面的“查找”操作實現。

並查集例題

並查集題目描述

若某個家族人員過於龐大，要判斷兩個是否是親戚，確實還很不容易，現在給出某個親戚關係圖，求任意給出的兩個人是否具有親戚關係。

並查集輸入

第一行：三個整數

分別表示有

個人，

個親戚關係，詢問

對親戚關係。

以下

行：每行兩個數

，

，表示

和

具有親戚關係。

接下來

行：每行兩個數

，

，詢問

和

是否具有親戚關係。

並查集輸出

共

行，每行一個’Yes’或’No’。表示第

個詢問的答案為“有”或“沒有”親戚關係。

並查集分析問題

初步分析覺得本題是一個圖論中判斷兩個點是否在同一個連通子圖中的問題。對於題目中的樣例，以人為點，關係為邊，建立無向圖如下：

比如判斷3和4是否為親戚時，我們檢查3和4是否在同一個連通子圖中，結果是在，於是他們是親戚。又如7和10不在同一個連通子圖中，所以他們不是親戚。

用圖的數據結構的最大問題是，我們無法存下多至(M=)2 000 000條邊的圖，後面關於算法時效等諸多問題就免談了。

用圖表示關係過於“奢侈”了。其實本題只是一個對分離集合（並查集）操作的問題。

例如樣例：

9 7 1

2 4

5 7

1 3

8 9

1 2

5 6

2 3

1 9

我們可以給每個人建立一個集合，集合的元素值有他自己，表示最開始時他不知道任何人是它的親戚。以後每次給出一個親戚關係a, b，則a和他的親戚與b和他的親戚就互為親戚了，將a所在集合與b所在集合合併。對於樣例數據的操作全過程如下：

初始狀態：{1} {2} {3} {4} {5} {6} {7} {8} {9}

輸入關係分離集合

(2,4) {2,4}{1} {3} {5} {6} {7} {8} {9}

(5,7) {2,4} {5,7} {1} {3} {6} {8} {9}

(1,3) {1,3} {2,4} {5,7}{6} {8} {9}

(8,9) {1,3} {2,4} {5,7} {8,9}{6}

(1,2) {1,2,3,4} {5,7} {8,9}{6}

(5,6) {1,2,3,4} {5,6,7} {8,9}

(2,3) {1,2,3,4} {5,6,7} {8,9}

判斷親戚關係

(1,9)，因為1,9不在同一集合內，所以輸出"NO"。

最後我們得到3個集合{1,2,3,4}、{5,6,7}、{8,9}，於是判斷兩個人是否親戚的問題就變成判斷兩個數是否在同一個集合中的問題。如此一來，需要的數據結構就沒有圖結構那樣龐大了。

算法需要以下幾個子過程：

(1) 開始時，為每個人建立一個集合FSY_ak_ioi(x)；

(2) 得到一個關係a b，合併相應集合FSY_ak_noi(a,b)；

(3) 此外我們還需要判斷兩個人是否在同一個集合中，這就涉及到如何標識集合的問題。我們可以在每個集合中選一個代表標識集合，因此我們需要一個子過程給出每個集合的代表元FSY_ak_csp(a)。於是判斷兩個人是否在同一個集合中，即兩個人是否為親戚，等價於判斷FSY_ak_csp(a)=FSY_ak_csp(b)。

有了以上子過程的支持，我們就有如下算法。

PROBLEM-Relations(N, M, a1,…,aM, b1,…,bM, Q, c1,…,cQ, d1,…,dQ)

for i←1 to N

do FSY_ak_ioi(i)

for i←1 to M

do if FSY_ak_csp(ai) != FSY_ak_csp(bi)

then FSY_ak_noi(ai, bi)

for i←1 to Q

do if FSY_ak_csp(ci)=FSY_ak_csp(di)

then output “Yes”

else output “No”

解決問題的關鍵便為選擇合適的數據結構實現並查集的操作，使算法的實現效率最高。

並查集注意事項

本題的輸入數據量很大，這使得我們的程序會在輸入中花去不少時間。如果你用Pascal寫程序，可以用庫函數SetTextBuf為輸入文件設置緩衝區，這可以使輸入過程加快不少。如果你是用C語言的話，就不必為此操心了，系統會自動分配緩衝區。

並查集單鏈表

一個節點對應一個人，在同一個集合中的節點串成一條鏈表就得到了單鏈表的實現。在集合中我們以單鏈表的第一個節點作為集合的代表元。於是每個節點x（x也是人的編號）應包含這些信息：指向代表元即表首的指針head[x]，指向表尾的指針tail[x]，下一個節點的指針next[x]。

SUB-Make-Set(x)過程設計如下：

SUB-Make-Set(x)

10 head[x]←x

11 tail[x]←x

12 next[x]←NIL

求代表元的SUB-Find-Set(x)過程設計如下：

SUB-Find-Set(x)

13 return head[x]

前兩個過程比較簡單，SUB-Union(a,b)稍微複雜一點。我們要做的是將b所在鏈表加到a所在鏈表尾，然後b所在鏈表中的所有節點的代表元指針改指a所在鏈表的表首節點。

過程的偽代碼如下：

SUB-Union(a,b)

14 next[tail[head[a]]]←head[b]

15 tail[head[a]]←tail[head[b]]

16 p←head[b]

17 while p != NIL

18 do head[p]←head[a]

19 p←next[p]

我們來分析一下算法的時間效率。SUB-Make-Set(x)和SUB-Find-Set(x)都只需要O(1)的時間，而SUB-Union(a,b)的時間效率與b所在鏈表的長度成線性關係。最壞情況下，即有操作序列SUB-Union(N-1,N), SUB-Union(N-2,N-1), …, SUB-Union(1,2)時，整個算法PROBLEM-Relations的時間複雜度為O(N+M+N^2+Q)=O(N^2+M+Q)。

由於算法的時間複雜度中O(M+Q)是必需的，因此我們要讓算法更快，就要考慮如何使減小O(N^2)。

我們想到合併鏈表時，我們可以用一種啓發式的方法：將較短的表合併到較長表上。為此每個節點中還需包含表的長度的信息。這比較容易實現，我們就不寫出偽代碼了。

時間複雜度。

首先我們給出一個固定對象x的代表元指針head[x]被更新次數的上界。由於每次x的代表元指針被更新時，x必然在較小的集合中，因此x的代表元指針被更新一次後，集合至少含2個元素。類似地，下一次更新後，集合至少含4個元素，繼續下去，當x的代表元指針被更新 log k 次後，集合至少含k個元素，而集合最多含n個元素，所以x的代表元指針至多被更新 log n 次。所以M次SUB-Union(a,b)操作的時間複雜度為O(NlogN+M)。算法總的時間複雜度為O(NlogN+M+Q)。

並查集森林

並查集的另一種更快的實現是用有根樹來表示集合：每棵樹表示一個集合，樹中的節點對應一個人。圖示出了一個並查集森林。

每個節點x包含這些信息：父節點指針p[x]，樹的深度rank[x]。其中rank[x]將用於啓發式合併過程。

於是建立集合過程的時間複雜度依然為O(1)。

SUB-Make-Set(x)

20 p[x]←x

21 rank[x]←0

用森林的數據結構來實現的最大好處就是降低SUB-Union(a,b)過程的時間複雜度。

SUB-Union(a,b)

22 SUB-Link(SUB-Find-Set(a),SUB-Find-Set(b))

SUB-Link(a,b)

23 p[a]←b

合併集合的工作只是將a所在樹的根節點的父節點改為b所在樹的根節點。這個操作只需O(1)的時間。而SUB-Union(a,b)的時間效率決定於SUB-Find-Set(x)的快慢。

SUB-Find-Set(x)

24 if x=p[x]

25 then return x

26 else return SUB-Find-Set(p[x])

這個過程的時效與樹的深度成線性關係，因此其平均時間複雜度為O(logN)，但在最壞情況下（樹退化成鏈表），時間複雜度為O(N)。於是PROBLEM-Relations最壞情況的時間複雜度為O(N(M+Q))。有必要對算法進行優化。

第一個優化是啓發式合併。在優化單鏈表時，我們將較短的錶鏈到較長的表尾，在這裏我們可以用同樣的方法，將深度較小的樹指到深度較大的樹的根上。這樣可以防止樹的退化，最壞情況不會出現。SUB-Find-Set(x)的時間複雜度為O(log N)，PROBLEM-Relations時間複雜度為O(N + logN (M+Q))。SUB-Link(a,b)作相應改動。

SUB-Link(a,b)

27 if rank[a]>rank

28 then p←a

29 else p[a]←b

30 if rank[a]=rank

31 then rank←rank+1

然而算法的耗時主要還是花在SUB-Find-Set(x)上。

第二個優化是路徑壓縮。它非常簡單而有效。在SUB-Find-Set(1)時，我們“順便”將節點1, 2, 3的父節點全改為節點4，以後再調用SUB-Find-Set(1)時在平均情況下就只需反阿克曼函數（接近O(1)）的時間。在最壞情況下仍為O(log)，但一般情況下此類數據很難構造。若同時使用路徑壓縮與啓發式合併優化，那麼複雜度就是嚴格的反阿克曼函數。

於是SUB-Find-Set(x)的代碼改為：

SUB-Find-Set(x)

32 if x≠p[x]

33 then p[x]←SUB-Find-Set(p[x])

34 return p[x]

該過程首先找到樹的根，然後將路徑上的所有節點的父節點改為這個根。實現時，遞歸的程序有許多棧的操作，改成非遞歸會更快些。

SUB-Find-Set(x)

35 r←x

36 while r≠p[r]

37 do r←p[r]

38 while x?r

39 do q←p[x]

40 p[x]←r

41 x←q

42 return r

改進後的算法時間複雜度的分析十分複雜，如果完整的寫出來足可寫一節，這裏我們只給出結論：改進後的PROBLEM-Relations其時間複雜度為O(N+(M+Q)*A(M+Q,N))，其中A(M+Q,N)為Ackerman函數的增長極為緩慢的逆函數。你不必瞭解與Ackerman函數相關的內容，只需知道在任何可想象得到的並查集數據結構的應用中，A(M+Q,N)≤4，因此PROBLEM-Relations的時間複雜度可認為是線性的O(N+M+Q)。

並查集優化路徑

並查集思想

每次查找的時候，如果路徑較長，則修改信息，以便下次查找的時候速度更快。

並查集實現

第一步，找到根結點。

第二步，修改查找路徑上的所有節點，將它們都指向根結點。

並查集代碼

#include<bits/stdc++.h>
#define fsy using
#define ak namespace
#define ioi std
fsy ak ioi;
const int M = 1e3 + 10 ;
int n , m ;
int folk[M] ;
int dsu (int u) { 
        return u == folk[u] ? u : folk[u] = dsu (folk[u]) ;
}
int main () {
        int n ;
        scanf ("%d" , &n) ;
        for (int i = 0 ; i < n ; i ++) folk[i] = i ;
        scanf ("%d" , &m) ;
        while (m --) {
                int u , v ;
                scanf ("%d%d" , &u , &v) ;
                int _u = dsu (u) , _v = dsu (v) ;
                if (_u != _v) {
                        folk[_v] = _u ;
                }
        }
        for (int i = 0 ; i < n ; i ++) dsu (i) ;
        return 0 ;
}

圖示

圖示-圖1

並查集代碼

並查集Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main{
    private static int father[];
    public static void main(String[]args)throws Exception{
            StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            while(st.nextToken() != StreamTokenizer.TT_EOF){
                int n=(int)st.nval;
                father=new int[n+1];
                for(int i=1;i<=n;i++){
                    father[i]=i;
                }
                st.nextToken();
                int m=(int)st.nval;
                st.nextToken();
                int p=(int)st.nval;
                for(int i=0;i<m;i++){
                    st.nextToken();
                    int a=(int)st.nval;
                    st.nextToken();
                    int b=(int)st.nval;
                    union(a,b);
                }
 
                for(int i=0;i<p;i++){
                    st.nextToken();
                    int a=(int)st.nval;
                    st.nextToken();
                    int b=(int)st.nval;
                    a=findParent(a);
                    b=findParent(b);
                    System.out.println(a==b?"Yes":"No");
                }
            }
    }
    private static void union(int f,int t){
        int a=findParent(f);
        int b=findParent(t);
        if(a==b)return;
        if(a>b){
            father[a]=b;
        }
        else {
            father[b]=a;
        }
    }
    private static int findParent(int f){
        while(father[f]!=f){
            f=father[f];
        }
        return f;
    }
}

並查集C++

class UnionFind{
public:
	UnionFind(int size): unionFind_(size, -1){ }
    int Find(int node){
    	return unionFind_[node] == -1 ? node : find(unionFind_[node]);
    }
    void Union(int node1, int node2){
    	unionFind_[Find(node2)] = Find(node1);
    }
private:
	vector<int> unionFind_;
}

並查集Pascal

var
  father:array[1..5000] of longint;
  i,j,k,p,n,m:longint;
  
function getfather(v:longint):longint;//尋找根節點
begin
  if father[v]=v then
    exit(v);
  father[v]:=getfather(father[v]);
  exit(father[v]);
end;

procedure merge(x,y:longint);//合併兩集合
var
  xx,yy:longint;
begin
  xx:=getfather(x);
  yy:=getfather(y);
  father[xx]:=yy;
end;

function judge(x,y:longint):boolean;//判斷是否在一集合中
var
  xx,yy:longint;
begin
  xx:=getfather(x);
  yy:=getfather(y);
  exit(xx=yy);
end;
begin
  readln(n,m,p);
  for i:=1 to n do
    father[i]:=i;
  for i:=1 to m do
    begin
      readln(j,k);
      merge(j,k);
    end;
  for i:=1 to p do
    begin
      readln(j,k);
      if judge(j,k) then
        writeln('Yes')
      else
        writeln('No');
    end;
end.

並查集的概述圖（2張）

詞條統計

瀏覽次數：次
編輯次數：91次歷史版本
最近更新：如人饮水553 （2023-12-04）

並查集

目錄

並查集主要操作

並查集初始化

並查集查找

並查集合併

並查集例題

並查集題目描述

並查集輸入

並查集輸出

並查集分析問題

並查集注意事項

並查集單鏈表

並查集森林

並查集優化路徑

並查集思想

並查集實現

並查集代碼

並查集代碼

並查集Java

並查集C++

並查集Pascal