并查集知识小结，欢迎交流，指正错误。
1. 并查集
并查集（Union-Find Sets）是一种非常精巧而实用的数据结构，只有合并和查找操作的数据结构，它主要用于处理一些不相交集合的合并问题。
可以查看该博客对并查集有个了解和认识，本人觉得该博客讲的还是不错的。
2. 并查集的实现
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
29
30
31
32
33
34
35
36
|
class UnionFind {
private int[] record; // 记录每个元素的上一级是谁
private int count; //剩余集合数目
// 初始化record[], 让每一个元素在最初始时的上一级是自己
public UnionFind(int n) {
record = new int[n];
for (int i = 0;i < n;i++) {
record[i] = i;
}
count = n;
}
// 寻找 p 元素所在集合的"根元素"
public int find(int p) {
// 路径压缩
if (p != record[p]) record[p] = find(record[p]);
return record[p];
}
// 合并 p 元素和 q 元素所在的集合
public void union(int p, int q) {
int pid = find(p);
int qid = find(q);
if (pid == qid) return;
// 合并
record[pid] = qid;
count--;
}
// 返回当前剩余的集合数
public int count() {
return count;
}
}
|
3. 并查集的应用
题目描述：
某一群岛由 n 个小岛组成，为了加强小岛居民之间的交流，首领决定启动一个造桥工程，将全部 n 个小岛连接到一起。
由于受到经融危机的影响，头目要求造桥的总成本要最少，并且规定每一座桥的成本都不能超过 k 万金币。
需要注意的是，由于受到地理环境和气候影响，有些小岛之间没办法直接造桥。
现给定 m 条小岛之间的造桥成本数据以及 k 的值，请问该工程是否能够顺利完成？
注意：可能桥的数量不够，也可能费用超支。
输入描述：
多组输入，第一行输入一个正整数 T 表示输入数据的组数。
对于每一组输入数据：输入 m+1 行。
第一行包含3个正整数，分别表示 n、m 和 k ，n <= 100, m <= 1000, k <= 10000 ，数字之间用空格隔开。
接下来 m 行表示 m 条小岛之间的造桥成本数据，每一行包含3个正整数，分别表示两个小岛的编号（从1开始）和造桥的成本（单位：万）。
输出描述：
针对每一组输入数据，如果工程能够完成输出“YES”，否则输出“NO”。
基本思路：
可以认为能够成功造桥的两个岛之间属于同一个岛屿，即将这两个岛合并（union）到一个岛屿中。最后如果剩余的岛屿数量为 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
57
58
|
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
for (int i = 0; i < T; i++) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
UnionFind unionFind = new UnionFind(n);
for (int j = 0; j < m; j++) {
int p = scanner.nextInt();
int q = scanner.nextInt();
int cost = scanner.nextInt();
if (cost <= k) {
unionFind.union(p, q);
}
}
if (unionFind.count() == 1) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}
}
class UnionFind {
private int[] record; // 记录每个元素的上一级是谁
private int count; // 岛屿的数量，
public UnionFind(int n) {
record = new int[n+1];
for (int i = 0;i <= n;i++) {
record[i] = i;
}
count = n;
}
public int find(int p) {
// 路径压缩
if (p != record[p]) record[p] = find(record[p]);
return record[p];
}
public void union(int p, int q) {
int pid = find(p);
int qid = find(q);
if (pid == qid) return;
// 合并
record[pid] = qid;
count--;
}
public int count() {
return count;
}
}
}
|
PS：当然该题也可以通过构造图的方法来解，最后用DFS来确认连通图的数量，为 1 表示成功；否则表示失败。
4. 其他
其他并查集的应用，LeetCode 547. 朋友圈 。