算法图算法

用并查集中各集合的代表元建图，处理集合级信息

字数统计: 1.5k字   |   阅读时长: 7分
,

摘要: 只用并查集中各集合的代表元建图

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

本文我们来看一个并查集的高级应用，先用并查集将节点分类并维护集合级信息。然后只用集合的代表元建图，对集合级信息进行后处理得到最终结果。本题是第 212 周赛 D 题。

$1 题目

给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的秩。

每个元素的 秩 是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：

  • 如果一个元素是它所在行和列的最小值，那么它的 秩 为 1。
  • 如果两个元素 p 和 q 在 同一行 或者 同一列 ，那么：
    • 如果 p < q ，那么 rank(p) < rank(q)
    • 如果 p == q ，那么 rank(p) == rank(q)
    • 如果 p > q ，那么 rank(p) > rank(q)
  • 秩 需要越 小 越好。

题目保证按照上面规则 answer 数组是唯一的。

提示：

1
2
3
4
m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-1e9 <= matrix[row][col] <= 1e9

示例 1：
输入：matrix = [[1,2],[3,4]]
输出：[[1,2],[2,3]]
解释：
matrix[0][0] 的秩为 1 ，因为它是所在行和列的最小整数。
matrix[0][1] 的秩为 2 ，因为 matrix[0][1] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。
matrix[1][0] 的秩为 2 ，因为 matrix[1][0] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。
matrix[1][1] 的秩为 3 ，因为 matrix[1][1] > matrix[0][1]， matrix[1][1] > matrix[1][0] 且 matrix[0][1] 和 matrix[1][0] 的秩都为 2 。

示例 2：
输入：matrix = [[7,7],[7,7]]
输出：[[1,1],[1,1]]

示例 3：
输入：matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
输出：[[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

示例 4：
输入：matrix = [[7,3,6],[1,4,5],[9,8,2]]
输出：[[5,1,4],[1,2,3],[6,3,1]]

$2 题解

算法: 拓扑排序+并查集

将所有值排序，值小的，秩也小。因此思路是就按照排序后的顺序从小到大分配秩。

但是当值相同的时候，同行以及同列的相同的值对应的位置，秩需要相同，值相同的这些点，不清楚以什么顺序去分配秩，因为当前位置分配秩的可能分配小了，后面值相同的位置更新了更大的秩时需要将当前位置的秩也更新。

因为同行以及同列的相同的值对应的位置需要整体考虑，因此可以将其视为一个连通分量，在更新秩时候更新整体。实现这个思路可以用带集合级的权的并查集。

首先按照同行以及同列的值相同这个关系将连通分量连边。然后按照同行同列值的大小关系建图，建图时只用代表元。然后在建好的图上拓扑排序，拓扑排序过程中，每一层的秩分配为同一个值，分配的值维护在并查集的代表元的权中。

代码 (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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
class UnionFindSet
{
public:
    UnionFindSet(int N)
    {
        _father.assign(N, -1);
        _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;
        }
        else
        {
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

    void update(int x, int val)
    {
        x = _find(x);
        _weight[x] = max(_weight[x], val);
    }

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

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

private:
    vector<int> _father;
    vector<int> _rank;
    vector<int> _weight; // idx -> val;

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

class Solution {
public:
    vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int N = n * m;
        vector<vector<int>> g(N);
        vector<int> indegrees(N, -1);
        map<int, vector<int>> mapping;
        UnionFindSet unionfindset(N);
        // 维护连通分量的并查集
        for(int i = 0; i < n; ++i)
        {
            mapping.clear();
            for(int j = 0; j < m; ++j)
                mapping[matrix[i][j]].push_back(i * m + j);
            auto it = mapping.begin();
            while(it != mapping.end())
            {
                if((it -> second).size() > 1)
                    for(int u: it -> second)
                        unionfindset.merge(u, (it -> second)[0]);
                ++it;
            }
        }
        for(int j = 0; j < m; ++j)
        {
            mapping.clear();
            for(int i = 0; i < n; ++i)
                mapping[matrix[i][j]].push_back(i * m + j);
            auto it = mapping.begin();
            while(it != mapping.end())
            {
                if((it -> second).size() > 1)
                    for(int u: it -> second)
                        unionfindset.merge(u, (it -> second)[0]);
                ++it;
            }
        }

        // 仅用代表元建图
        for(int i = 0; i < n; ++i)
        {
            mapping.clear();
            for(int j = 0; j < m; ++j)
                mapping[matrix[i][j]].push_back(i * m + j);
            auto it = mapping.begin();
            int start = unionfindset.get_root((it -> second)[0]);
            if(indegrees[start] == -1)
                indegrees[start] = 0;
            while(next(it) != mapping.end())
            {
                int u = unionfindset.get_root((it -> second)[0]);
                int v = unionfindset.get_root((next(it) -> second)[0]);
                if(indegrees[v] == -1)
                    indegrees[v] = 0;
                ++indegrees[v];
                g[u].push_back(v);
                ++it;
            }
        }
        for(int j = 0; j < m; ++j)
        {
            mapping.clear();
            for(int i = 0; i < n; ++i)
                mapping[matrix[i][j]].push_back(i * m + j);
            auto it = mapping.begin();
            int start = unionfindset.get_root((it -> second)[0]);
            if(indegrees[start] == -1)
                indegrees[start] = 0;
            while(next(it) != mapping.end())
            {
                int u = unionfindset.get_root((it -> second)[0]);
                int v = unionfindset.get_root((next(it) -> second)[0]);
                if(indegrees[v] == -1)
                    indegrees[v] = 0;
                ++indegrees[v];
                g[u].push_back(v);
                ++it;
            }
        }

        // 拓扑排序
        queue<int> q;
        for(int i = 0; i < N; ++i)
        {
            int u = unionfindset.get_root(i);
            if(u != i)
                continue;
            if(indegrees[u] == 0)
            {
                q.push(u);
                unionfindset.update(u, 1);
            }
        }
        vector<int> level_nodes;
        int level = 1;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            for(int u: level_nodes)
            {
                for(int v: g[u])
                {
                    --indegrees[v];
                    if(indegrees[v] == 0)
                    {
                        q.push(v);
                        unionfindset.update(v, level + 1);
                    }
                }
            }
            ++level;
        }

        vector<vector<int>> result(n, vector<int>(m, -1));
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                result[i][j] = unionfindset.query(i * m + j);
        return result;
    }
};
Share