The Suspects以及并查集总结

Posted on | In |
Words count in article: 2.3k

The Suspects以及并查集总结

  • 题目
  • 基本并查集
  • Size优化并查集
  • Rank优化并查集
  • 路径压缩优化一(最好)
  • 路径压缩优化二(递归)

题目链接

http://poj.org/problem?id=1611

题意

就是告诉你0号同学被感染了，他还参加了一些社团，给出一些社团以及里面的人，问总共多少人感染。输入给出n表示人数(标号为0~n-1)，m表示社团数目，接下来m行每行第一个数k ，表示该社团有k人，然后是k个人的编号。要你输出有多少个人感染了病毒。

在这里插入图片描述

解析

题目本身并不难:

  • 把每个社团加入到各自的集合中，然后不断的合并相同的集合，最后看哪些和0号同学在同一个集合中，使用一个变量记录和0号同学在同一个集合中的人数即可；
  • 这里主要是总结并查集几种优化的方式；

基本并查集

基本并查集，记录一个每个结点p的父亲结点是parent[p]，然后是一个不断从孩子找父亲的过程:

  • find()操作， while(p != parent[p])p = parent[p]，一直往上找根的过程；
  • union()操作，就是找到两个结点的根节点，然后将其中一个结点的根节点挂到另一个结点的根节点即可；

例如: union()操作合并6和3所在的集合:
这里写图片描述

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
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    static class UnionSet {
        private int[] parent;

        public UnionSet(int size) {
            parent = new int[size];
            /** 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合 */
            for (int i = 0; i < size; i++)
                parent[i] = i;
        }

        public int size() {
            return parent.length;
        }

        // 查找过程, 查找元素p所对应的集合编号
        private int find(int p) {
            if (p < 0 || p >= parent.length)
                throw new IllegalArgumentException("p is out of bound.");
            while (p != parent[p])
                p = parent[p];
            return p;
        }

        public boolean isSameSet(Integer a, Integer b) {
            return find(b) == find(a);
        }

        // 合并元素p和元素q所属的集合
        public void union(int a, int b) {
            int aRoot = find(a);
            int bRoot = find(b);
            if (aRoot == bRoot)
                return;
            parent[aRoot] = bRoot;
        }
    }


    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        while (cin.hasNext()) {
            int n = cin.nextInt();
            int m = cin.nextInt();
            if (n == 0 && m == 0)
                break;
            UnionSet unionSet = new UnionSet(n);

            for (int i = 0; i < m; i++) {
                int k = cin.nextInt();
                int root = cin.nextInt();
                for (int j = 0; j < k - 1; j++) { //k-1个
                    int x = cin.nextInt();
                    unionSet.union(root, x); //这个集合的根
                }
            }
            int sum = 1; //0号已经被感染
            for (int i = 1; i < n; i++) {
                if (unionSet.isSameSet(0, i)) {
                    sum++;
                }
            }
            System.out.println(sum);
        }
    }
}

Size优化并查集

  • 在union()操作中，有一种情况会使得我们的集合变得深度很深，这对查询来说是会降低效率的；
  • 例如下面的union，合并3和9所在的集合，如果我们将3的根8挂在9下面，会使得高度变成4：(不好的）；

这里写图片描述
于是，我们的解决办法是:

  • 每一个集合记录一个size，在union()操作的时候，我们将size小的挂到size大的下面，这样会使得深度稍微小一点；
  • 操作完之后记得维护被挂的那个集合的size()；

这里写图片描述

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
static class UnionSet{
    private int[] parent;
    private int[] sz;     // sz[i]表示以i为根的集合中元素个数

    public UnionSet(int size) {
        parent = new int[size];
        sz = new int[size];
        /** 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合 */
        for( int i = 0 ; i < size ; i ++ ) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    public int size(){
        return parent.length;
    }

    private int find(int p){
        if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");
        while(p != parent[p])
            p = parent[p];
        return p;
    }

    public boolean isSameSet(Integer a, Integer b){
        return find(b) == find(a);
    }

    public void union(int a,int b){
        int aRoot = find(a);
        int bRoot = find(b);
        if(aRoot == bRoot)
            return;

        /**
         * 根据两个元素所在树的元素个数不同判断合并方向
         * 将元素个数少的集合合并到元素个数多的集合上
         */
        if(sz[aRoot] < sz[bRoot]){
            parent[aRoot] = bRoot;
            sz[bRoot] += sz[aRoot];
        }else {
            parent[bRoot] = aRoot;
            sz[aRoot] += sz[bRoot];
        }
    }
}

Rank优化并查集

  • 基于rank的优化，其中rank[i]表示的是根节点为i的树的高度；

发现问题:

  • 虽然上面的size优化已经很不错，但是如果出现下面的情况，例如合并0和3所在的集合，如下，这样会使得高度变成4，而如果反着合并就只需要变成3；
  • 于是我们需要记录的不是size，而是记录一个高度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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
static class UnionSet{
    private int[] parent;
    private int[] rank;   // rank[i]表示以i为根的集合所表示的树的层数

    public UnionSet(int size) {
        parent = new int[size];
        rank = new int[size];
        for( int i = 0 ; i < size ; i ++ ) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int size(){
        return parent.length;
    }

    private int find(int p){
        if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");
        while(p != parent[p])
            p = parent[p];
        return p;
    }

    public boolean isSameSet(Integer a, Integer b){
        return find(b) == find(a);
    }

    public void union(int a,int b){
        int aRoot = find(a);
        int bRoot = find(b);
        if(aRoot == bRoot)
            return;

        /**
         *根据两个元素所在树的rank不同判断合并方向
         *将rank低的集合合并到rank高的集合上
         */
        if(rank[aRoot] < rank[bRoot])
            parent[aRoot] = bRoot; // a 挂在 b 下
        else if(rank[bRoot] < rank[aRoot])
            parent[bRoot] = aRoot;
        else {  //rank[aRoot] == rank[bRoot]
            parent[aRoot] = bRoot; // a 挂在　b 下
            rank[bRoot]++; //此时维护rank的值
        }

    }
}

路径压缩优化一(最好)

并查集另一个优化就是路径压缩:

  • 例如下面的三个集合是等价的，但是查询的效率确实逐渐的增加的，第一个查询效率最低，第三个查询效率最高；
  • 我们需要做的就是在find()的时候，沿途将查找的孩子结点改变他们的父亲parent达到路径压缩的目的；

这里写图片描述

首先来看改造成第二个版本: (使用非递归 )

  • 这个优化就是对于沿途的结点，我们从底到上，依次更改他们的父亲结点为他们的父亲结点的父亲结点(parent[p] = parent[parent[p]] )；
  • 例如我们查询find(4)，第一步，我们先将parent[4] = 2，（2就是4的父亲(3)的父亲）；

这里写图片描述

  • 继续往上，把2的父亲结点改为2的父亲结点的父亲结点，也就是0结点，此时我们的树结构变成了下面的样子；

这里写图片描述
于是我们就完成了从第一种情况到第二种情况的优化:

这里写图片描述

  • 代码如下： 在代码中的更改只有上一个版本中find()函数中增加了一行代码: parent[p] = parent[parent[p]]；
    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
    static class UnionSet{
        private int[] parent;

        /**
         *  在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
         *  这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
         */
        private int[] rank;

        public UnionSet(int size) {
            parent = new int[size];
            rank = new int[size];
            for( int i = 0 ; i < size ; i ++ ) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int size(){
            return parent.length;
        }

        private int find(int p){
            if(p < 0 || p >= parent.length)
                throw new IllegalArgumentException("p is out of bound.");
            while(p != parent[p]) {
                /** p这个结点的父亲设置为它父亲的父亲   ,  相对于第三个版本只增加了这一行代码 */
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public boolean isSameSet(Integer a, Integer b){
            return find(b) == find(a);
        }

        public void union(int a,int b){
            int aRoot = find(a);
            int bRoot = find(b);
            if(aRoot == bRoot)
                return;

            if(rank[aRoot] < rank[bRoot])
                parent[aRoot] = bRoot;
            else if(rank[bRoot] < rank[aRoot])
                parent[bRoot] = aRoot; 
            else {
                parent[aRoot] = bRoot;
                rank[bRoot]++;
            }

        }
    }

路径压缩优化二(递归)

继续完成从第一种情况到第三种情况的优化，其实核心代码只有几行: 

1
2
3
4
5
private int find(int p){
    if(p != parent[p])
        parent[p] = find(parent[p]);
    return parent[p];
}
  • 我们宏观的就是将parent[p]执行了最终的那个根节点，并返回了；

这里写图片描述
这里写图片描述

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
static class UnionSet{
    private int[] parent;
    private int[] rank;

    public UnionSet(int size) {
        parent = new int[size];
        rank = new int[size];
        for( int i = 0 ; i < size ; i ++ ) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int size(){
        return parent.length;
    }

    private int find(int p){
        if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");

        /**和上一种路径压缩不同的是　这里使用的是递归　会将所有的孩子都直接挂在根下面*/
        if(p != parent[p])
            parent[p] = find(parent[p]);
        return parent[p];
    }

    public boolean isSameSet(Integer a, Integer b){
        return find(b) == find(a);
    }

    public void union(int a,int b){
        int aRoot = find(a);
        int bRoot = find(b);
        if(aRoot == bRoot)
            return;

        if(rank[aRoot] < rank[bRoot])
            parent[aRoot] = bRoot;
        else if(rank[bRoot] < rank[aRoot])
            parent[bRoot] = aRoot;
        else {
            parent[aRoot] = bRoot;
            rank[bRoot]++;
        }

    }
}

POJ上测试效率对比，从下到上，从版本一到版本五的时间:

这里写图片描述

欢迎关注我们的公众号
© 2021 — 2024 true | Site words total count: 328.5k
Theme — NexT.Pisces v5.1.4
0%