# Road Map

# 并查集概念

(Union-Find Set)，也称为不相交集数据结构（Disjointed Set Data Structure），指一系列不相交的集合(Sets)，提供合并（Union）和查找(Find)两种操作。总结：一种用来 解决集合查询合并 的数据结构，支持 近乎 O(1)的 find 操作 和 近乎 O(1)的 union 操作

# 基本操作

# 并查集初始化

初始化每个节点的都属于自己的单独集合

int f[N];
for (int i = 0; i< n ; i++) f[i] = i;

1
2

# find(int i)

判断是否属于同一集合

$find(i)$ 即查找 $i$ 所归属的集合，通常我们使用 $find(i)$ 和find(j)判断 $i$ 和 $j$ 是否连通，即是否属于同一个集合

int find(int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]); // 路径压缩
}

1
2
3
4

# union(int i , int j)

将两个集合进行合并

顾名思义，union 方法即将 I 和 J 所在的两个集合连通起来，执行这个方法后，I 所在集合所有元素和 J 所在集合的所有元素都连通

void unionFather(int x, int y){
  	if (find(x) != find(y)) {
      // x 合并到 y; 谁的老大哥被改变了，谁就是被合并了；
      f[find(x)] = find(y);
    }
}

1
2
3
4
5
6

合并的是父节点：老大哥之间合并，跟小弟没关系

限制合并顺序，将值较大的合并至值较小的

void uni(int x, inty){
  int p = find(x), q = find(y);
	if (p == q) return;
  if (p > q) swap(p, q);
  f[q] = p; // p 的值 比 q 小，把更大的合并到更小的
}

1
2
3
4
5
6

# 完整版代码

int f[N];
for (int i = 0; i < n; i++)f[i] = i; // 构造

int find(int x) { // 查询
    if (f[x] == x) return x;
    return f[x] = find(f[x]); // 路径压缩
}
/**
 * 合并; 当find(x) != find(y) 才进行合并；
 * 如果find(x) == find(y)，没必要进行合并，已经在一个集合；此时进行合并会出现环路，造成find查询出问题；
 **/
void u(int x, int y) {
    if (find(x) != find(y)) {
      f[find(x)] = find(y);
    }
}

bool isOneSet(int x, int y) return find(x)==find(y);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 带 rank 的路径压缩实现（了解）

class Solution {
public:
    void makeSet(int n){
        vector<int> p(n, 0);
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        vector<int> rank(n, 0);
    }
    int find(vector<int> &p, int x) {
        if (p[x] != x) {
            p[x] = find(p, p[x]);  //路径压缩
        }
        return p[x];
    }
    void unionSet(vector<int> &p, vector<int> &rank, int x, int y) {
        x = find(p, x);
        y = find(p, y);
        if (rank[x] < rank[y]) p[x]= y;
        else {
            p[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
    }
};

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

# 适用场景

有 N 个点，用 M 条线进行两两相连的操作（相连即为合并操作）

# 判断两点是否连通

如果 $find(A) == find(B)$ ，则 A 与 B 连通

# 求连通块的数量

for i:0~n
  cnt += i == p[i]

1
2

# 求连通块的节点数

for i:0~n;
    find(A) == find(i) && cnt++

1
2

# 判断是否存在环路

进行合并操作时，先判断是否连通，如果已经连通，则存在环路

注意：此时进行合并会死循环

# 题目精选

# 图论相关

# 547. 省份数量 (opens new window)

就是求连通块的个数

class Solution {
    int[] f;

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        f = new int[n];
        for (int i = 0; i < n; i++) f[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    un(i, j);
                }
            }
        }

        int cnt = 0;
        for (int i =0; i<n; i++){
            if (i == f[i]) cnt++ ;
        }
        return cnt;
    }
    int find(int x) {
        if (x == f[x]) return x;
        return f[x] = find(f[x]);
    }
    void un(int x, int y) {
        if (find(x) != find(y)) f[find(x)] = find(y);
    }
}

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

# 岛屿问题

# 简单集合合并

LeetCode 128. Longest Consecutive Sequence (hard) (opens new window)

# 拓展阅读

算法导论-第 21 章:用于不想交集合的数据结构


class Solution {
  int[] p;
  int n;
  public int findCircleNum(int[][] cnn) {
    n = cnn.length;
    p = new int[n];
    for (int i = 0; i < n; i++)p[i] = i;

    for (int i = 0; i< n; i++){
      for (int j = i+1; j< n; j++){
      	if (cnn[i][j] == 1 && find(i) != find(j)) {
        	p[find(i)] = find(j);
        }
      }
    }

    int cnt  = 0;
    for (int i = 0; i< n; i++){
      if (i == p[i])cnt++;
    }
    return cnt;
  }
  int find(int x){
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
  }
}

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

← 0x42_单调栈 0x45_扫描线 →