光与影的个人博客

NEUCoder

0%

并查集整理

发表于 更新于 分类于 ，

什么是并查集

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。

百度百科

并查集包括两种操作：

  1. find(x) 查询元素所属的集合
  2. union(x, y) 合并两个不相关的集合

我理解的并查集，就是对于一系列元素，不同元素组成不同的集合（使用树的形式描述集合），多个集合共同构成并查集（森林），提供集合与集合的合并（两棵的合并）和 查找元素所属的集合（在哪棵树）

如何实现并查集

并查集中只关注元素属于哪个集合，集合之间的合并操作，以树形式表示集合，每个元素只需要知道自己所属树的根节点就能知道自己属于哪个集合(属于哪个树)，集合合并也可转化为树的合并，因此可使用类似于完全二叉树的数组存储方式实现并查集。

存储结构实现：

  • 使用father数组，存储元素的父节点(不直接存储根节点的原因在于，合并操作无法保证该性质)

  • 每个元素初始化父节点为本身，表示并查集初始每个元素自成一个集合

    int father[elements];

操作实现：

  1. find(x) 查询元素所属集合

    1
    2
    3
    4
    5
    6
    7
    8
    // 不断的向上查询父节点，直到找到当前集合的根
    int find(x){
    	root = x;
    	while(father[root] != root){
    		parent = father[root];
    	}
    	return root;
    }

  2. union 合并集合操作

    • 找到两个集合的根节点，将其中一个根节点父节点设置为另一集合根节点
    1
    2
    3
    4
    5
    6
    7
    int uninon(x,y){
    	int root_x = find(x)
    	int root_y = find(y)
    	// 以x插入到y为例
    	parent[root_x] = root_y
        return root_y
    }

  • java实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public class DisjointSetUnion {
        private int[] parent;
        public DisjointSetUnion(int nums){
            parent = new int[nums];
            //初始化
            for(int i = 0;i < nums;i++){
                parent[i] = i;
            }
        }
        public int find(int x){
            while(parent[x] != x){
                x = parent[x];
            }
            return x;
        }
        public int union(int x,int y){
            int parent_x = find(x);
            int parent_y = find(y);
            parent[parent_x] = parent_y;
            return parent_y;
        }
    }

并查集优化

1.路径压缩降低查找集合标示的复杂度

在find的过程中，直接将当前的根节点接到所在集合的根节点

  • 该方法只有在查询的过程中才会优化，且只优化树的一条路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int find(x){
	if(father[x] == x){
		return x;
	}
	else{
        //同样的找父根节点，增加了赋值操作
		father[x] = find(father[x]);
        return father[x];
	}
}

//一行简写法
int find(int x)
{
    return x == father[x] ? x : (father[x] = find(fa[x]));
}
2.按秩合并的方式

出发点是把简单的树往复杂的树上合并，以减少合并增加的平均树深度，定义节点的秩为以当前节点为根子树的深度，开辟秩数组，每个节点对应一个秩。

初始化方法修改为：

1
2
3
4
5
6
7
8
9
//所有的秩均初始化为1
void init(int n){
	father = new int[n];
	rank = new int[n];
	for(int i = 0;i < n;i++){
		father[i] = i;
		rank[i] = i;
	}
}

合并方法修改为：

1
2
3
4
5
6
7
8
9
10
11
12
void union(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    //深度相同时，根节点深度+1,深度不同，插入子树不影响深度
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   
}

并查集应用

  1. 洛谷p1551 亲戚问题

    • 简答的并查集思路，求是否具有亲戚关系，即判断两元素是否在一个集合中

    • 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
      37
      38
      39
      40
      41
      42
      43
      44
      import java.util.Scanner;
      class Main{
          static int[] parent;

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

          public static int union(int x,int y){
              int parent_x = find(x);
              int parent_y = find(y);
              parent[parent_x] = parent_y;
              return parent_y;
          }
          public static void main(String[] args) {
              Scanner scanner = new Scanner(System.in);
              int n,m,p;
              n = scanner.nextInt();
              m = scanner.nextInt();
              p = scanner.nextInt();

              //初始化并查集
              parent = new int[n];
              for(int i = 0;i < parent.length;i++){
                  parent[i] = i;
              }
              //读取关系合并并查集
              for(int i = 0;i < m;i++){
                  union(scanner.nextInt() - 1,scanner.nextInt() - 1);
              }
              //判断两个集合是否在同一个集合中
              for(int i = 0;i < p;i++){
                  if(find(scanner.nextInt() - 1) == find(scanner.nextInt() - 1)){
                      System.out.println("Yes");
                  }
                  else {
                      System.out.println("No");
                  }
              }
          }
      }

  2. 岛屿数量问题(LC 200. 岛屿数量)

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
class Solution {
    //并查集方法
    class DisjointUnion{
        int count;
        int[] parents;
        int[] rank;
        public DisjointUnion(char[][] grid){
            this.count = 0;
            this.parents = new int[grid.length * grid[0].length];
            this.parents = new int[grid.length * grid[0].length];
            this.rank = new int[grid.length * grid[0].length];
            //初始化集合，每个元素1自成一个集合
            for(int i = 0;i < grid.length;i++){
                for(int j = 0;j < grid[0].length;j++){
                    if(grid[i][j] == '1'){
                        this.count++;
                        //集合标识为自己
                        parents[i * grid[0].length + j] = i * grid[0].length + j;
                    }
                    this.rank[i * grid[0].length + j] = 1;
                }
            }
        }

        public int find(int x){
            if(x != parents[x]){
                parents[x] = find(parents[x]);
                x = parents[x];
            }
            return x;
        }

        public void union(int x, int y){
            int parentX = find(x);
            int parentY = find(y);
            //是否为不同的集合
            if(parentX != parentY){
                this.count--;

                //添加秩的合并操作
                if(rank[parentX] <= rank[parentY]){
                    parents[parentX] = parentY;
                }
                else{
                    parents[parentY] = parentX;
                    if(rank[parentX] == parentY){
                        rank[parentY]++;
                    }
                }
            }
        }
        public int getCount(){
            return this.count;
        }
    }
    public int numIslands(char[][] grid) {
        DisjointUnion disjointUnion = new DisjointUnion(grid);
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] == '1'){
                    if(i - 1 >= 0 && grid[i - 1][j] == '1'){
                        disjointUnion.union(i * grid[0].length + j, (i - 1) * grid[0].length + j);
                    }
                    if(j - 1 >= 0 && grid[i][j - 1] == '1'){
                        disjointUnion.union(i * grid[0].length + j, i * grid[0].length + j - 1);
                    }
                    if(i + 1 < grid.length && grid[i + 1][j] == '1'){
                        disjointUnion.union(i * grid[0].length + j, (i +1) * grid[0].length + j);
                    }
                    if(j + 1 < grid[0].length && grid[i][j + 1] == '1'){
                        disjointUnion.union(i * grid[0].length + j, i * grid[0].length + j + 1);
                    }
                }
            }
        }
        return disjointUnion.getCount();
    }
}