算法图算法

删边连通性：并查集+逆向思维

字数统计: 1.8k字   |   阅读时长: 8分
, ,

摘要: 并查集+逆向思维处理删边连通性问题

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

对于维护加边连通性的过程，并查集是非常有力的。

但是由于并查集合并后一般是不支持回滚的，仅仅可以通过开栈的方式实现撤销合并，即回滚一步。

因此如果要维护一个删边连通性的过程，并查集就无法完成了。但是有些问题可以逆向思维，即正向思维是 初态图 -> 删边 -> 终态图，逆向思维就变成了 终态图 -> 加边 -> 初态图，如果这个逆向思维可行，那么就可以利用逆向思维+并查集维护删边连通性。

下面我们看一个相关的题目。

803. 打砖块

有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

  • 一块砖直接连接到网格的顶部，或者
  • 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时

给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 掉落 。一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

提示：

1
2
3
4
5
6
7
8
9
m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] 为 0 或 1
1 <= hits.length <= 4 * 1e4
hits[i].length == 2
0 <= xi <= m - 1
0 <= yi <= n - 1
所有 (xi, yi) 互不相同

示例 1：
输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：网格开始为：
[[1,0,0,0]，
[1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
[0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
[0,0,0,0]]
因此，结果为 [2] 。

示例 2：
输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：网格开始为：
[[1,0,0,0],
[1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
[1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0],
[1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
[0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。

分析

本题有一个初始状态的图，然后给定了一系列删边操作，在删边的过程中需要维护连通分量大小的变化。

即每删一条边，问这一删会造成多少个原来连接在带标记的连通分量上的节点脱离了带标记的连通分量。

逆向思维

由于所有删边操作都给出来了，因此可以直接先得到删边后的终态图。

在终态图上加边，每加一条边，问有多少原来没有连接到带标记的连通分量上的节点现在连接上了。

这一问是并查集可以维护的加边连通性问题。

算法：并查集 + 逆向思维

在初始图上将删除序列中的点标记为0。之后用剩下的1根据关系在并查集中连边，就可以得到删边后最终的连通分量。

这些连通分量有些是带标记的，有些是不带标记的。后续加边过程需要考察这个标记。

维护标记的算法：所有图里的节点将标记置为 false，将目标的节点打上标记 true。以后合并的时候，如果有其中一个根带标记 true，则新根也带标记 false。

1
2
3
4
5
在初始图上将删除序列中的点标记为0得到终态图
将目标节点，即与顶部连接的节点打上标记
根据终态图给并查集连边，连边过程中维护连通分量大小和代表元的标记
倒序枚举删除序列，将删除的边视为加边:
    执行加边合并的过程返回一个值，表示有多少无标记的连通分量与有标记的连通分量连上了

代码 (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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        _father.assign(n, -1);
        _rank.assign(n, 0);
        _weight.assign(n, 1);
        _label.assign(n, false);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
    }

    void set_label(int x)
    {
        _label[_find(x)] = true;
    }

    bool check_label(int x)
    {
        return _label[_find(x)];
    }

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

        int ans = 0;
        if(!_label[x] && _label[y])
            ans = _weight[x];
        else if(_label[x] && !_label[y])
            ans = _weight[y];

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

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

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

class Solution {
public:
    vector<int> hitBricks(const vector<vector<int>>& grid, vector<vector<int>>& hits) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> new_grid = grid;
        for(vector<int> &coord: hits)
            new_grid[coord[0]][coord[1]] = 0;
        UnionFindSet unionfindset(n * m);
        for(int j = 0; j < m; ++j)
            unionfindset.set_label(j);
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(new_grid[i][j] == 0)
                    continue;
                if(visited[i][j])
                    continue;
                visited[i][j] = true;
                dfs(new_grid, unionfindset, i, j, visited);
            }
        int M = hits.size();
        vector<int> result(M);
        for(int k = M - 1; k >= 0; --k)
        {
            int i = hits[k][0], j = hits[k][1];
            if(grid[i][j] == 0)
                continue;
            int u = i * m + j;
            int cnt = 0;
            bool label = unionfindset.check_label(u);
            for(int d = 0; d < 4; ++d)
            {
                int x = i + dx[d], y = j + dy[d];
                if(x < 0 || x >= n || y < 0 || y >= m)
                    continue;
                if(new_grid[x][y] == 1)
                {
                    int v = x * m + y;
                    int c = unionfindset.merge(u, v);
                    cnt += c;
                }
            }
            if(cnt > 0)
            {
                result[k] = cnt - 1;
                if(label)
                    ++result[k];
            }
            new_grid[i][j] = 1;
        }
        return result;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    void dfs(const vector<vector<int>>& new_grid, UnionFindSet& unionfindset, int i, int j, vector<vector<bool>>& visited)
    {
        int n = new_grid.size(), m = new_grid[0].size();
        int u = i * m + j;
        for(int d = 0; d < 4; ++d)
        {
            int x = i + dx[d], y = j + dy[d];
            if(x < 0 || x >= n || y < 0 || y >= m)
                continue;
            if(new_grid[x][y] == 0)
                continue;
            if(visited[x][y])
                continue;
            visited[x][y] = true;
            int v = x * m + y;
            unionfindset.merge(u, v);
            dfs(new_grid, unionfindset, x, y, visited);
        }
    }
};
Share