并查集

学习并查集之前：图论？一个记忆化 DFS 爆搜完事！

学习并查集之后：什么叫做优雅啊！

模板(无注释)

Java

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
private class UnionFind {
    private int[] parent;
    
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        parent[rootX] = rootY;
    }
    
    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

C++

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
class UnionFind {
public:
    UnionFind(int n) {
        for (int i = 0; i < n; ++i) {
            parent.push_back(i);
        }
    }

    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    void my_union(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);
        parent[root_x] = root_y;
    }

    bool is_connected(int x, int y) {
        return find(x) == find(y);
    }
private:
    vector<int> parent;
};
  • 类成员应该使用 vector<int> 而不是 int[]。或者使用 int*
  • union 是 C++ 中的一个关键字，应换名

优化

路径压缩

发生在 Find 的过程中，将目标节点到根节点路径上的所有目标节点的祖先节点的 parent 域全部改为根节点。这样可以有效缩小树的高度。

一般而言，路径压缩有「隔代压缩」和「完全压缩」两种，上面所描述的将路径山的全部节点的 parent 域都修改为根节点的是完全压缩。

而「隔代压缩」是指，将当前待 find 节点的 parent 改为其 parent 的 parent

按秩合并

发生在 Union 的过程中，即将秩较小的树挂在秩较大的树上，这样可以使得新生成的树的高度不会太高。

问题来了，什么是秩 Rank？

秩一般是指树的高度，但是由于路径压缩会破坏树原有的结构、且树的高度不易维护，因此，常常将「树的节点树」定义为树的秩。

模板(有注释)

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
private class UnionFind {
	private int[] parent; // 每个节点的parent域指向其父节点的下标。其实就是树的双亲表示法
    
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 初始时每个节点都是自己的根节点，自成一树
        }
    }
    
    // 将返回下标为x的节点的根节点的下标
    // 在find的过程中进行路径压缩
    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // 这行代码用于隔代压缩
            x = parent[x];
        }
        return x;
    }
    
    // 将下标为x和下标为y的两个节点各自所在的子树进行合并
    public void union(int x, int y) {
        // 分别找到两个节点各自的根节点
        int a = find(x);
        int b = find(y);
        // 不必进行按秩合并了
        parent[a] = b;
    }
    
    // 判断下标为x和y的两个节点是否在同一个集合中
    // i.e. 是否具有相同的根节点
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

例题

LC 990

典型的并查集应用题。

由于仅有 26 个小写字母，那么将并查集的大小设为 26。

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
class Solution {
    public boolean equationsPossible(String[] equations) {
        var helper = new UnionFind(26);
        for (String eq: equations) {
            if (eq.charAt(1) == '=') {
                char left = eq.charAt(0);
                char right = eq.charAt(3);
                // union
                if (left == right) {
                    continue;
                }
                helper.union(left - 'a', right - 'a');
            } else {
                continue;
            }
        }
        for (String ne: equations) {
            if (ne.charAt(1) == '!') {
                char left = ne.charAt(0);
                char right = ne.charAt(3);
                // check if they are connected
                if (left == right) {
                    return false;
                }
                if (helper.isConnected(left - 'a', right - 'a')) {
                    return false;
                }
            } else {
                continue;
            }
        }
        return true;
    }
}

LC 1319

一道稍微难一点的并查集应用题。

我们首先创建一个大小为 n 的并查集。

我们遍历 connections 数组进行 Union 操作。在每次 Union 开始前，我们先检查两台主机是否已经连通，如果已经连通，那么说明这根网线便可以「节省下来」。将节省下来的网线的数量记为 spare。

此外，我们额外维护一个不相交集合的数量 cnt。如果最终所有的主机可以连通，那么 cnt 应为 1。所以，如果 spare 大于等于 cnt - 1，返回 cnt - 1，否则返回 -1

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
class Solution {
    public int makeConnected(int n, int[][] connections) {
        var helper = new UnionFind(n);
        int spare = 0;
        for (int[] each: connections) {
            int left = each[0];
            int right = each[1];
            if (helper.isConnected(left, right)) {
                spare++;
            } else {
                helper.union(left, right);
            }
        }
        if (spare >= helper.getCnt() - 1) {
            return helper.getCnt() - 1;
        } else {
            return -1;
        }
    }
    private class UnionFind {
        private int[] parent;
        private int cnt;
        public UnionFind(int n) {
            parent = new int[n];
            cnt = n;
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
            }
        }
    
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                cnt--;
            }
            parent[rootX] = rootY;
        }
    
        public int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
    
        public boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }

        public int getCnt() {
            return cnt;
        }
    }
}

LC 684

并查集的简单应用。

扫描一遍 edges 中的各边。扫描到 edge 时，检查两个顶点是否已经连通。如果已经连通，那么这个 edge 成为候选答案，但由于题目要求返回最后出现的边，所以继续向后扫描；如果没有连通，那么将这两个顶点进行 Union。

注意，由于题目中所给的节点值均从 1 开始，因此不要忘了 -1，即第 7 和 8 行

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
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        var helper = new UnionFind(n);
        int[] ans = null;
        for (int[] edge: edges) {
            int left = edge[0] - 1;
            int right = edge[1] - 1;
            if (helper.isConnected(left, right)) {
                ans = edge;
            } else {
                helper.union(left, right);
            }
        }
        return ans;
    }
    private class UnionFind {
        private int[] parent;
    
        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
            }
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            parent[rootX] = rootY;
        }
    
        public int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
    
        public boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }
    }
}

LC 261

并查集运用题，如果了解树的性质的话可以使得编码更加简洁。

在一个有 n 个节点的树中（不只是二叉树），边的个数为 n - 1。

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
class UnionFind {
public:
    UnionFind(int n) {
        for (int i = 0; i < n; ++i) {
            parent.push_back(i);
        }
    }

    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    bool my_union(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);
        if (root_x != root_y) {
            parent[root_x] = root_y;
            return true;
        } else {
            parent[root_x] = root_y;
            return false;
        }
    }

    bool is_connected(int x, int y) {
        return find(x) == find(y);
    }
private:
    vector<int> parent;
};

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) {
            return false;
        }
        UnionFind* helper = new UnionFind(n);
        for (auto edge: edges) {
            int left = edge[0];
            int right = edge[1];
            if (!helper->my_union(left, right)) {
                return false;
            }
        }
        return true;
    }
};

LC 323

连通分量即并查集中不相交集合的数量

LC 924

并查集的简单应用。注意，当一个连通分量仅有一个节点在 initial 数组中时，删除这个节点，才可以保证整个连通分量都可以不被感染。因此我们要事先统计一下每个连通分量中，在 initial 的节点数量 cnts。对于 initial 中的每个节点 x，当 cnts[find(x)]==1 时，删除这个 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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// UnionFind usage:
//
// uf := &UnionFind{}
//
// uf.init(n)
type UnionFind struct {
	n      int
	parent []int
	size   []int
}

func (union *UnionFind) init(sz int) {
	union.n = sz
	union.parent = make([]int, sz)
	union.size = make([]int, sz)
	for i := 0; i < sz; i++ {
		union.parent[i] = i
		union.size[i] = 1
	}
}
func (union *UnionFind) find(x int) int {
	for union.parent[x] != x {
		union.parent[x] = union.parent[union.parent[x]]
		x = union.parent[x]
	}
	return x
}
func (union *UnionFind) union(x, y int) {
	if union.isConnected(x, y) {
		return
	}
	rootX := union.find(x)
	rootY := union.find(y)
	szX := union.size[rootX]
	szY := union.size[rootY]
	if szX > szY {
		union.parent[rootY] = rootX
		union.size[rootX] += szY
	} else {
		union.parent[rootX] = rootY
		union.size[rootY] += szX
	}
}
func (union *UnionFind) isConnected(x, y int) bool {
	return union.find(x) == union.find(y)
}
func (union *UnionFind) getCap(x int) int {
	return union.size[x]
}
func minMalwareSpread(graph [][]int, initial []int) int {
	n := len(graph)
	uf := &UnionFind{}
	uf.init(n)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if graph[i][j] == 1 {
				uf.union(i, j)
			}
		}
	}
	sort.Ints(initial)
	idx := initial[0]
	sz := 0
	cnts := make([]int, n)
	for i := 0; i < len(initial); i++ {
		cur := initial[i]
		parent := uf.find(cur)
		cnts[parent]++
	}
	for i := 0; i < len(initial); i++ {
		cur := initial[i]
		// find its parent
		parent := uf.find(cur)
		if cnts[parent] != 1 {
			continue
		}
		if uf.getCap(parent) > sz {
			sz = uf.getCap(parent)
			idx = cur
		}
	}
	return idx
}
study
#算法 #数据结构
并查集
https://exapricity.tech/Union-Find.html
作者
Peiyang He
发布于
2023年3月3日
许可协议