DisjointSet 並查集 學習筆記

Posted on Edited on In , Views:

學習影片：Bilibili左程云【算法讲解056【必备】并查集-上】

概述

解決集合、快速合併的問題
各種操作所花費的時間，均攤後時間複雜度幾乎為O(1)

方法概要與原理

  1. int find(a) 找出a所在的集合中的代表
  2. bool isSameSet(a, b) 回傳a, b是否屬於同個集合
  3. void union(a, b) 將a所在的集合的所有元素與b所在的集合的所有元素合併，變成一個新的集合

兩個陣列:
father[]: f[i] 所對應的就是 index 的 father，初始每個i對應的都是自己 f[i] = i
size[]: size[i] 所在的集合的大小，用於union的優化

優化:

  • 必須: 扁平化(路徑壓縮) -> find
  • 可選: 小掛大 -> union

基礎版code

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
int n; // target n
vector<int> f(MAXN);

void build(){
  for(int i=0; i<n; ++i){
    f[i] = i;
  }
}

int find(int a){
  return ((f[a] == a) ? a : (f[a] = find(f[a])));
}

bool isSameSet(int a, int b){
  return find(a) == find(b);
}

void Union(int a, int b){
  int fa = find(a);
  int fb = find(b);
  if(fa != fb){ // 是同一個集合就不用union
    // 小掛大優化
    if(size[fa] >= size[fb]){ // fb 掛 fa
      size[fa] += size[fb];
      f[fb] = fa;
    }
    else{ // fa 掛 fb
      size[fb] += size[fa];
      f[fa] = fb;
    }
  }
}

練習題目與題解

牛客NowCoder 並查集的實現
洛谷LuoGu 【模板】并查集