岛屿数量（并查集）

题目

给你一个由’1’（陆地）和’0’（水）组成的二维网格，请你计算网格钟岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

  • 示例1：

    1
    2
    3
    4
    5
    6
    7
    输入: grid = [
    	["1", "1", "1", "1", "0"],
    	["1", "1", "0", "1", "0"],
    	["1", "1", "0", "0", "0"],
    	["0", "0", "0", "0", "0"]
    ]
    输出: 1

  • 示例2：

    1
    2
    3
    4
    5
    6
    7
    输入: grid = [
    	["1", "1", "0", "0", "0"],
    	["1", "1", "0", "0", "0"],
    	["0", "0", "1", "0", "0"],
    	["0", "0", "0", "1", "1"]
    ]
    输出: 3

思路+代码

本题解可以采用DFS（深度优先搜索）、BFS（广度优先搜索）、并查集的方式完成解题。但是本篇文章重点介绍并查集的方法，并帮助读者理解并查集

并查集理论

并查集（union & find）：用于处理一些元素合并和查询问题，主要包含三个方法与三个属性

  • find(x)方法：确定x元素属于哪一个子集（寻找x元素的根节点）。实现方法采用路径压缩方式
  • isConnected(p, q)：用于判断两个元素是否属于同一个子集，即两元素是否连通
  • union(p, q)：将两个元素所在的子集进行合并（前提是两个元素所在子集不连通）
  • count：并查集总数（子集个数）
  • parent：数组记录每个节点的父节点索引
  • 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class UnionFind{
public:
	UnionFind(vector<vector<char>>& grid){
		int rows = grid.size();
		int cols = grid[0].size();
		count = 0;  //之前忘记了
		for (int r = 0; r < rows; r++)
		{
			for (int c = 0; c < cols; c++)
			{
				if (grid[r][c] == '1')
				{
					parent.push_back(r * cols + c);
					count++;    //之前忘记了
				}
				else
					parent.push_back(-1);
				rank.push_back(0);
			}
		}
	}

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

	void unite(int x, int y){
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root)
		{
			return;
		}
		else
		{
			if (rank[x_root] < rank[y_root])
			{
				int temp = rank[x_root];
				rank[x_root] = rank[y_root];
				rank[y_root] = temp;
			}
			parent[y_root] = x_root;
			if (rank[x_root] == rank[y_root])
				rank[x_root]++;
			count--;    //之前忘记了
			return;
		}
	}

	bool isConnected(int x, int y){
		if (find(x) == find(y))
			return true;
		else
			return false;
	}

	int getCount(){
		return count;
	}
private:
	int count;
	vector<int> parent;
	vector<int> rank;
};

基于并查集类完成岛屿数量的题解

并查集可以代替树结构对邻近“岛屿”（“1”）进行搜索

  • 思路：扫描整个二维网格，如果该位置为“1”，则将其与相邻四个方向上的“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
    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            int rows = grid.size();
            int cols = grid[0].size();
            UnionFind uf(grid);
            for (int r = 0; r < rows; r++)
            {
                for (int c = 0; c < cols; c++)
                {
                    if (grid[r][c] == '1')
                    {
                        grid[r][c] = '0';
                        if (r-1 >= 0 && grid[r-1][c] == '1')
                            uf.unite(r * cols + c, (r-1) * cols + c);
                        if (r+1 < rows && grid[r+1][c] == '1')
                            uf.unite(r * cols + c, (r+1) * cols + c);
                        if (c-1 >= 0 && grid[r][c-1] == '1')
                            uf.unite(r * cols + c, r * cols + c - 1);
                        if (c+1 < cols && grid[r][c+1] == '1')
                            uf.unite(r * cols + c, r * cols + c + 1);
                    }
                }
            }
            return uf.getCount();
        };
    };

辅助理解资料

按秩合并

  • 按秩合并可以通过减少森林的深度，来节约之后搜索的时间
    例如有如下两个树型集合：

    将A集合合并到D集合，合并后树的深度是3，而将D合并到A上，深度就变为4。因此在并查集类的合并方法中，只有当两个集合树的深度一样时，将两者合并后深度会+1，其余情况合并后深度为A、B集合深度的较大者，即：max(A,B)

路径压缩

  • 路径压缩是为了防止出现树的不平衡状态，即为单分支树。采用路径压缩，只需要n(1)的时间复杂度即可找到父节点
  • 当数据过大，递归会导致爆栈，所以需要用非递归算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int find(int x)
    {
    	int k, j, r;
    	r = x;
    	while(r != parent[r])
    		r = parent[r];
    	k = x;        
    	while(k != r) 
    	{
    		j = parent[k]; 
    		parent[k] = r; 
    		k = j; 
    	}
    	return r; 
    }

算法步骤流程

  • 如下示例：
    1
    2
    3
    4
    5
    6
    7
    输入: grid = [
    	["1", "1", "1"],
    	["0", "1", "0"],
    	["1", "0", "0"],
    	["1", "0", "1"]
    ]
    输出: 3
  • parent和rank数组变化情况表：
    0 1 2 3 4 5 6 7 8 9 10 11 count
    parent1 0 1 2 -1 4 -1 6 -1 -1 9 -1 11
    rank1 0 0 0 0 0 0 0 0 0 0 0 0 7
    parent2 0 0 2 -1 4 -1 6 -1 -1 9 -1 11
    rank2 1 0 0 0 0 0 0 0 0 0 0 0 6
    parent3 0 0 0 -1 4 -1 6 -1 -1 9 -1 11
    rank3 1 0 0 0 0 0 0 0 0 0 0 0 5
    parent4 0 0 0 -1 0 -1 6 -1 -1 9 -1 11
    rank4 1 0 0 0 0 0 0 0 0 0 0 0 4
    parent5 0 0 0 -1 0 -1 6 -1 -1 6 -1 11
    rank5 1 0 0 0 0 0 1 0 0 0 0 0 3


来源：LeetCode
链接：并查集、岛屿官方题解
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。