跳转至

並查集

引入

並查集是一種用於管理元素所屬集合的數據結構，實現為一個森林，其中每棵樹表示一個集合，樹中的節點表示對應集合中的元素。

顧名思義，並查集支持兩種操作：

  • 合併（Union）：合併兩個元素所屬集合（合併對應的樹）
  • 查詢（Find）：查詢某個元素所屬集合（查詢對應的樹的根節點），這可以用於判斷兩個元素是否屬於同一集合

並查集在經過修改後可以支持單個元素的刪除、移動；使用動態開點線段樹還可以實現可持久化並查集。

Warning

並查集無法以較低複雜度實現集合的分離。

初始化

初始時，每個元素都位於一個單獨的集合，表示為一棵只有根節點的樹。方便起見，我們將根節點的父親設為自己。

實現 
1
2
3
4
5
struct dsu {
  vector<size_t> pa;

  explicit dsu(size_t size) : pa(size) { iota(pa.begin(), pa.end(), 0); }
};

1
2
3
class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))

查詢

我們需要沿着樹向上移動，直至找到根節點。

實現 
1
size_t dsu::find(size_t x) { return pa[x] == x ? x : find(pa[x]); }

1
2
def find(self, x):
    return x if self.pa[x] == x else self.find(self.pa[x])

路徑壓縮

查詢過程中經過的每個元素都屬於該集合，我們可以將其直接連到根節點以加快後續查詢。

實現 
1
size_t dsu::find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

1
2
3
4
def find(self, x):
    if self.pa[x] != x:
        self.pa[x] = self.find(self.pa[x])
    return self.pa[x]

合併

要合併兩棵樹，我們只需要將一棵樹的根節點連到另一棵樹的根節點。

實現 
1
void dsu::unite(size_t x, size_t y) { pa[find(x)] = find(y); }

1
2
def union(self, x, y):
    self.pa[self.find(x)] = self.find(y)

啓發式合併

合併時，選擇哪棵樹的根節點作為新樹的根節點會影響未來操作的複雜度。我們可以將節點較少或深度較小的樹連到另一棵，以免發生退化。

具體複雜度討論

由於需要我們支持的只有集合的合併、查詢操作，當我們需要將兩個集合合二為一時，無論將哪一個集合連接到另一個集合的下面，都能得到正確的結果。但不同的連接方法存在時間複雜度的差異。具體來説，如果我們將一棵點數與深度都較小的集合樹連接到一棵更大的集合樹下，顯然相比於另一種連接方案，接下來執行查找操作的用時更小（也會帶來更優的最壞時間複雜度）。

當然，我們不總能遇到恰好如上所述的集合——點數與深度都更小。鑑於點數與深度這兩個特徵都很容易維護，我們常常從中擇一，作為估價函數。而無論選擇哪一個，時間複雜度都為 \(O (m\alpha(m,n))\)，具體的證明可參見 References 中引用的論文。

在算法競賽的實際代碼中，即便不使用啓發式合併，代碼也往往能夠在規定時間內完成任務。在 Tarjan 的論文1中，證明了不使用啓發式合併、只使用路徑壓縮的最壞時間複雜度是 \(O (m \log n)\)。在姚期智的論文2中，證明了不使用啓發式合併、只使用路徑壓縮，在平均情況下，時間複雜度依然是 \(O (m\alpha(m,n))\)。

如果只使用啓發式合併，而不使用路徑壓縮，時間複雜度為 \(O(m\log n)\)。由於路徑壓縮單次合併可能造成大量修改，有時路徑壓縮並不適合使用。例如，在可持久化並查集、線段樹分治 + 並查集中，一般使用只啓發式合併的並查集。

按節點數合併的參考實現：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
struct dsu {
  vector<size_t> pa, size;

  explicit dsu(size_t size_) : pa(size_), size(size_, 1) {
    iota(pa.begin(), pa.end(), 0);
  }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    pa[y] = x;
    size[x] += size[y];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))
        self.size = [1] * size

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.pa[y] = x
        self.size[x] += self.size[y]

刪除

要刪除一個葉子節點，我們可以將其父親設為自己。為了保證要刪除的元素都是葉子，我們可以預先為每個節點製作副本，並將其副本作為父親。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
struct dsu {
  vector<size_t> pa, size;

  explicit dsu(size_t size_) : pa(size_ * 2), size(size_ * 2, 1) {
    iota(pa.begin(), pa.begin() + size_, size_);
    iota(pa.begin() + size_, pa.end(), size_);
  }

  void erase(size_t x) {
    --size[find(x)];
    pa[x] = x;
  }
};

1
2
3
4
5
6
7
8
class Dsu:
    def __init__(self, size):
        self.pa = list(range(size, size * 2)) * 2
        self.size = [1] * size * 2

    def erase(self, x):
        self.size[self.find(x)] -= 1
        self.pa[x] = x

移動

與刪除類似，通過以副本作為父親，保證要移動的元素都是葉子。

實現 
1
2
3
4
5
6
void dsu::move(size_t x, size_t y) {
  auto fx = find(x), fy = find(y);
  if (fx == fy) return;
  pa[x] = fy;
  --size[fx], ++size[fy];
}

1
2
3
4
5
6
7
def move(self, x, y):
    fx, fy = self.find(x), self.find(y)
    if fx == fy:
        return
    self.pa[x] = fy
    self.size[fx] -= 1
    self.size[fy] += 1

複雜度

時間複雜度

同時使用路徑壓縮和啓發式合併之後，並查集的每個操作平均時間僅為 \(O(\alpha(n))\)，其中 \(\alpha\) 為阿克曼函數的反函數，其增長極其緩慢，也就是説其單次操作的平均運行時間可以認為是一個很小的常數。

Ackermann 函數 \(A(m, n)\) 的定義是這樣的：

\(A(m, n) = \begin{cases}n+1&\text{if }m=0\\A(m-1,1)&\text{if }m>0\text{ and }n=0\\A(m-1,A(m,n-1))&\text{otherwise}\end{cases}\)

而反 Ackermann 函數 \(\alpha(n)\) 的定義是阿克曼函數的反函數，即為最大的整數 \(m\) 使得 \(A(m, m) \leqslant n\)。

時間複雜度的證明 在這個頁面中。

空間複雜度

顯然為 \(O(n)\)。

帶權並查集

我們還可以在並查集的邊上定義某種權值、以及這種權值在路徑壓縮時產生的運算，從而解決更多的問題。比如對於經典的「NOI2001」食物鏈，我們可以在邊權上維護模 3 意義下的加法羣。

例題

UVa11987 Almost Union-Find

實現類似並查集的數據結構，支持以下操作：

  1. 合併兩個元素所屬集合
  2. 移動單個元素
  3. 查詢某個元素所屬集合的大小及元素和
參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

using namespace std;

struct dsu {
  vector<size_t> pa, size, sum;

  explicit dsu(size_t size_)
      : pa(size_ * 2), size(size_ * 2, 1), sum(size_ * 2) {
    // size 与 sum 的前半段其实没有使用，只是为了让下标计算更简单
    iota(pa.begin(), pa.begin() + size_, size_);
    iota(pa.begin() + size_, pa.end(), size_);
    iota(sum.begin() + size_, sum.end(), 0);
  }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    pa[y] = x;
    size[x] += size[y];
    sum[x] += sum[y];
  }

  void move(size_t x, size_t y) {
    auto fx = find(x), fy = find(y);
    if (fx == fy) return;
    pa[x] = fy;
    --size[fx], ++size[fy];
    sum[fx] -= x, sum[fy] += x;
  }

  size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
};

int main() {
  size_t n, m, op, x, y;
  while (cin >> n >> m) {
    dsu dsu(n + 1);  // 元素范围是 1..n
    while (m--) {
      cin >> op;
      switch (op) {
        case 1:
          cin >> x >> y;
          dsu.unite(x, y);
          break;
        case 2:
          cin >> x >> y;
          dsu.move(x, y);
          break;
        case 3:
          cin >> x;
          x = dsu.find(x);
          cout << dsu.size[x] << ' ' << dsu.sum[x] << '\n';
          break;
        default:
          assert(false);  // not reachable
      }
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Dsu:
    def __init__(self, size):
        # size 与 sum 的前半段其实没有使用，只是为了让下标计算更简单
        self.pa = list(range(size, size * 2)) * 2
        self.size = [1] * size * 2
        self.sum = list(range(size)) * 2

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.pa[y] = x
        self.size[x] += self.size[y]
        self.sum[x] += self.sum[y]

    def move(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return
        self.pa[x] = fy
        self.size[fx] -= 1
        self.size[fy] += 1
        self.sum[fx] -= x
        self.sum[fy] += x

    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]


if __name__ == "__main__":
    while True:
        try:
            n, m = map(int, input().split())
            dsu = Dsu(n + 1)  # 元素范围是 1..n
            for _ in range(m):
                op_x_y = list(map(int, input().split()))
                op = op_x_y[0]
                if op == 1:
                    dsu.union(op_x_y[1], op_x_y[2])
                elif op == 2:
                    dsu.move(op_x_y[1], op_x_y[2])
                elif op == 3:
                    x = dsu.find(op_x_y[1])
                    print(dsu.size[x], dsu.sum[x])
        except EOFError:
            break

習題

「NOI2015」程序自動分析

「JSOI2008」星球大戰

「NOI2001」食物鏈

「NOI2002」銀河英雄傳説

其他應用

最小生成樹算法 中的 Kruskal 和 最近公共祖先 中的 Tarjan 算法是基於並查集的算法。

相關專題見 並查集應用。

參考資料與拓展閲讀

  1. 知乎回答：是否在並查集中真的有二分路徑壓縮優化？
  2. Gabow, H. N., & Tarjan, R. E. (1985). A Linear-Time Algorithm for a Special Case of Disjoint Set Union. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 30, 209-221.PDF

  1. Tarjan, R. E., & Van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM (JACM), 31(2), 245-281.ResearchGate PDF ↩

  2. Yao, A. C. (1985). On the expected performance of path compression algorithms.SIAM Journal on Computing, 14(1), 129-133. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：HeRaNO, JuicyMio, Xeonacid, sailordiary, ouuan
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用