算法图算法

并查集维护平面点的横纵坐标

字数统计: 2.2k字   |   阅读时长: 9分
,

摘要: 并查集的原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

此前我们详细学习过并查集的原理，比如 并查集、带边权的并查集、含集合级信息的并查集。

本文我们学习并查集的一个常见应用技巧：维护平面点的横纵坐标。然后解决力扣 947 和 1267。

场景：按规则维护平面坐标的连通性

考虑二维平面有 N 个点，每个点有一个坐标 (x, y)，每两个点，如果横坐标相同或纵坐标相同，则视为在同一个连通分量中。问给定的 N 个点构成多少个连通分量。

用并查集维护坐标点有两个办法：维护点编号、维护横纵坐标。

(1) 并查集维护点编号

并查集维护点的编号，枚举所有点对 i, j，如果横坐标相同或者纵坐标相同，则在并查集中合并 (i, j)，最终在并查集中可以直接得到连通分量个数

(2) 并查集维护横坐标和纵坐标

并查集维护横坐标和纵坐标，将横坐标的范围和纵坐标的范围映射到 (0, MAX)。

对于一个点编号 i，坐标 xi, yi。由于该点存在，横坐标为 xi 或者纵坐标为 yi 的其它点均会连通，因此可以直接把 xi 和 yi 在并查集中合并。

在用并查集维护坐标的基础上，最终的连通分量个数就是通过枚举点 i，将代表元插入哈希表，由哈希表执行去重，得到的去重后的代表元个数就是最终连通分量个数。

下面两个题目抽象之后都是这个场景问题，可以一起解决。

1267. 统计参与通信的服务器

这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。

如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

提示：

1
2
3
4
5
m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

示例 1：
输入：grid = [[1,0],[0,1]]
输出：0
解释：没有一台服务器能与其他服务器进行通信。

示例 2：
输入：grid = [[1,0],[1,1]]
输出：3
解释：所有这些服务器都至少可以与一台别的服务器进行通信。

示例 3：
输入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
输出：4
解释：第一行的两台服务器互相通信，第三列的两台服务器互相通信，但右下角的服务器无法与其他服务器通信。

代码 (C++)

本题就是前面第一部分的场景问题，分析过程参考前面，这里直接给出代码。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        _father.assign(n, 0);
        _rank.assign(n, 0);
        _weight.assign(n, 1);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y)
            return;

        if(_rank[x] < _rank[y])
        {
            _father[x] = y;
            _weight[y] += _weight[x];
        }
        else
        {
            _father[y] = x;
            _weight[x] += _weight[y];
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

    int get(int x)
    {
        return _weight[_find(x)];
    }

private:
    vector<int> _father;
    vector<int> _rank;
    vector<int> _weight;

    int _find(int x)
    {
        if(x == _father[x])
            return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        UnionFindSet unionfindset(n * m);
        vector<int> tmp;
        for(int i = 0; i < n; ++i)
        {
            tmp.clear();
            for(int j = 0; j < m; ++j)
            {
                if(grid[i][j] == 1)
                    tmp.push_back(i * m + j);
            }
            int M = tmp.size();
            for(int k = 1; k < M; ++k)
                unionfindset.merge(tmp[k - 1], tmp[k]);
        }
        for(int j = 0; j < m; ++j)
        {
            tmp.clear();
            for(int i = 0; i < n; ++i)
            {
                if(grid[i][j] == 1)
                    tmp.push_back(i * m + j);
            }
            int M = tmp.size();
            for(int k = 1; k < M; ++k)
                unionfindset.merge(tmp[k - 1], tmp[k]);
        }
        int ans = 0;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(grid[i][j] == 1 && unionfindset.get(i * m + j) > 1)
                    ++ans;
            }
        return ans;
    }
};

947. 移除最多的同行或同列石头

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

提示：

1
2
3
1 <= stones.length <= 1000
0 <= xi, yi <= 1e4
不会有两块石头放在同一个坐标点上

示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：

  1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
  2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
  3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
  4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
  5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
    石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。

示例 2：
输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：

  1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
  2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
  3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
    石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。

示例 3：
输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。

算法1: 并查集维护点编号

直接在并查集中维护所有实际的节点编号，及其连通性，枚举点对，如果同行或同列则加边。并在并查集内部维护连通分量个数。

代码 (C++)

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
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        _father.assign(n, 0);
        _rank.assign(n, 0);
        cc_num = n;
        for(int i = 0; i < n; ++i)
            _father[i] = i;
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y)
            return;

        if(_rank[x] < _rank[y])
        {
            _father[x] = y;
        }
        else
        {
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
        --cc_num;
    }

    int get_cc_num()
    {
        return cc_num;
    }

private:
    vector<int> _father;
    vector<int> _rank;
    int cc_num; // 连通分量个数

    int _find(int x)
    {
        if(x == _father[x])
            return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        UnionFindSet unionfindset(n);
        for(int i = 0; i < n - 1; ++i)
            for(int j = i + 1; j < n; ++j)
            {
                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])
                    unionfindset.merge(i, j);
            }
        return n - unionfindset.get_cc_num();
    }
};

算法: 并查集维护横坐标纵坐标

并查集不维护节点编号，而维护横坐标和纵坐标。根据横纵坐标的范围，横纵坐标可以到一个整数表示，并将所需空间一次性开出。例如横纵坐标范围均为 [0, 10000)，那么可以开出 20000 的空间，其中 [0, 10000) 表示横坐标，[10000, 20000) 表示纵坐标。

将并查集连边后，统计连通分量个数的过程：枚举点，查询该点的代表元，将代表元插入哈希表中，哈希表实现去重。

代码 (C++)

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
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        _father.assign(n, 0);
        _rank.assign(n, 0);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y)
            return;

        if(_rank[x] < _rank[y])
        {
            _father[x] = y;
        }
        else
        {
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

    int find(int x)
    {
        return _find(x);
    }

private:
    vector<int> _father;
    vector<int> _rank;

    int _find(int x)
    {
        if(x == _father[x])
            return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        // 0~9999 是行的范围 10000~19999 是列的范围
        UnionFindSet unionfindset(20000);
        unordered_set<int> setting; // 代表元
        for(int i = 0; i < n; ++i)
            unionfindset.merge(stones[i][0], 10000 + stones[i][1]);
        for(int i = 0; i < n; ++i)
            setting.insert(unionfindset.find(stones[i][0]));
        return n - setting.size();
    }
};
Share