1
class DisjointSet {
2
 private:
3
  vector<int> parent;
4
  vector<int> rank;
5
  int n;
6

7
 public:
8
  DisjointSet(int size) {
9
    n = size;
10
    parent.resize(size, 0);
11
    rank.resize(size, 0);
12
    for (int i = 0; i < size; i++) parent[i] = i;
13
  }
14
  int find(int x) {
15
    if (parent[x] != x) {
16
      parent[x] = find(parent[x]);
17
    }
18
    return parent[x];
19
  }
20
  bool merge(int x, int y) {
21
    int gX = find(x);
22
    int gY = find(y);
23
    if (gX == gY) return false;
24
    if (rank[gX] > rank[gY])
25
      parent[gY] = gX;
26
    else if (rank[gX] < rank[gY])
27
      parent[gX] = gY;
28
    else {
29
      parent[gY] = gX;
30
      rank[gX]++;
31
    }
32
    return true;
33
  }
34
  void reset() {
35
    for (int i = 0; i < n; i++) {
36
      parent[i] = i;
37
      rank[i] = 0;
38
    }
39
  }
40
};
41
class Solution {
42
 public:
43
  vector<vector<int>> matrixRankTransform(vector<vector<int>> &matrix) {
44
    int m = matrix.size();
45
    int n = matrix[0].size();
46
    vector<vector<int>> answer(m, vector<int>(n, 1));
47

48
    // mp:(sorted) value to positions
49
    map<int, vector<pair<int, int>>> mp;
50
    for (int i = 0; i < m; ++i) {
51
      for (int j = 0; j < n; ++j) {
52
        mp[matrix[i][j]].push_back(make_pair(i, j));
53
      }
54
    }
55

56
    vector<int> rowMax(m, 0);
57
    vector<int> colMax(n, 0);
58
    DisjointSet *disjointSet = new DisjointSet(m + n);
59
    vector<vector<pair<int, int>>> group2positions(m + n);
60
    for (auto &element : mp) {
61
      disjointSet->reset();
62
      group2positions.clear();
63
      group2positions.resize(m + n);
64

65
      // grouping positions with the same value by col and row
66
      for (auto &[x, y] : element.second) {
67
        disjointSet->merge(x, m + y);
68
      }
69
      // allocating the grouping results
70
      for (auto &[x, y] : element.second) {
71
        group2positions[disjointSet->find(x)].push_back(make_pair(x, y));
72
      }
73

74
      // for each group, assign the ranking
75
      for (auto &group : group2positions) {
76
        int rank = 1;
77
        // rank should be the max among members in group
78
        for (auto &[x, y] : group) {
79
          rank = max(rank, max(rowMax[x], colMax[y]) + 1);
80
        }
81
        // update the answer and max rank in row and col
82
        for (auto &[x, y] : group) {
83
          answer[x][y] = rank;
84
          rowMax[x] = rank;
85
          colMax[y] = rank;
86
        }
87
      }
88
    }
89
    return answer;
90
  }
91
};