并查集

用途

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

操作

  • 合并(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");
            }
        }
    }