并查集

用途

解决元素分组问题,管理一系列不相交的集合

操作

  • 合并(Union):把两个不相交的集合合并为一个集合
  • 查询(Find):查询两个元素是否在同一个集合

以一个应用场景为例应用场景

(洛谷P1551) 亲戚

题目背景
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
题目描述
规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。
输入格式
第一行:三个整数n,m,p,(n<=5000,m<=5000,p<=5000),分别表示有n个人,m个亲戚关系,询问p对亲戚关系。
以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表示Mi和Mj具有亲戚关系。
接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有亲戚关系。
输出格式
P行,每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

把所有人划分到若干个不相交的集合中,每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚,只需看它们是否属于同一个集合即可。因此,这里就可以考虑用并查集进行维护。

思想

用集合中的一个元素代表集合。我曾看过一个有趣的比喻,把集合比喻成帮派,而代表元素则是帮主。接下来我们利用这个比喻,看看并查集是如何运作的。

最开始,每个元素的代表元素是自己。每个元素的最顶端是自己,是一个自环节点。

在比较两人是不是一个帮派的时候,就找自己的帮主,看看是不是一个帮主。每个元素向上找,找到不能再找了就是了。

然而帮派规模大了,肯定会造成等级(树的深度)变深。

有两个操作可以优化一个是路径压缩,一个是按秩压缩。

之前说找帮主来判断两个元素是否在同一集合内。找到帮主一样说明是一个集合里的,不一样把较小集合的帮主指向较大集合的帮主,这样做就是按秩压缩:

按秩压缩了之后其实还是可以发现树是深度是越来越深的,那么再采取路径压缩。

在每次向上查找的过程中,将路过的节点之间指向帮主,这是通过栈来实现的。

代码

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
public class 并查集 {

// 样本进来会包一层,叫做元素
public static class Element<V> {
public V value;

public Element(V value) {
this.value = value;
}
}

public static class UnionFindSet<V> {

public HashMap<V, Element<V>> elementMap;
// key 某个元素value 该元素的父
public HashMap<Element<V>, Element<V>> fatherMap;
// key 某个集合的代表元素, value该集合的大小
public HashMap<Element<V>, Integer> sizeMap;

public UnionFindSet(List<V> list) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();

for (V value : list) {
Element element = new Element(value);
elementMap.put(value, element);
fatherMap.put(element, element);
sizeMap.put(element, 1);
}
}

// 给定一个element,网上找,把代表元素返回
private Element<V> findHead(Element<V> element) {
Stack<Element<V>> path = new Stack<>();
while (element != fatherMap.get(element)) {
path.push(element);
element = fatherMap.get(element);
}
while (!path.isEmpty()) { // 路径铺平
fatherMap.put(path.pop(), element);
}
return element;
}

public boolean isSameSet(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
}
return false;
}

public void union(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
Element<V> aF = findHead(elementMap.get(a));
Element<V> bF = findHead(elementMap.get(b));
if (aF != bF) {
Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
Element<V> small = big == aF ? bF : aF;
fatherMap.put(small, big);
sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
sizeMap.remove(small);
}
}
}

}


}

应用

洛谷P1551亲戚

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
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 人数
int m = scanner.nextInt(); // 关系数
int p = scanner.nextInt(); // 询问多少个关系

List<Integer> personList = new ArrayList<>();
int[][] relation = new int[m][2];
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
if (!personList.contains(p1)) personList.add(p1);
if (!personList.contains(p2)) personList.add(p2);
relation[i][0] = p1;
relation[i][1] = p2;
// relationMap.put(p2, p1);
}

UnionFindSet<Integer> unionSet = new UnionFindSet<>(personList);


// for (Map.Entry<Integer, Integer> entry : relationMap.entrySet()) {
// unionSet.union(entry.getKey(), entry.getValue());
// }

for (int i = 0; i < m; i++) {
unionSet.union(relation[i][0], relation[i][1]);
}

for (int i = 0; i < p; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
if (unionSet.isSameSet(p1, p2)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}