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
|
using namespace std;
int n, m;
const int maxn = 1e6 + 5;
int par[maxn];
int a[maxn];
int ord[maxn];
int tmp[maxn];
vector<int> G[maxn];
int deg[maxn];
int id[maxn];
int sz;
int ans[maxn];
int (int u){
return u == par[u] ? u : par[u] = find(par[u]);
}
bool cmp(int x, int y){
return tmp[x] < tmp[y];
}
void merge(int u, int v){
int fx = find(u);
int fy = find(v);
if(u == v) return;
par[fy] = fx;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n * m; i++) cin >> a[i], par[i] = i;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
tmp[j] = a[(i - 1) * m + j];
ord[j] = j;
}
sort(ord + 1, ord + 1 + m, cmp);
for(int j = 1; j < m; j++){
if(tmp[ord[j]] == tmp[ord[j + 1]]){
merge((i - 1) * m + ord[j], (i - 1) * m + ord[j + 1]);
}
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
tmp[j] = a[(j - 1) * m + i];
ord[j] = j;
}
sort(ord + 1, ord + 1 + n, cmp);
for(int j = 1; j < n; j++){
if(tmp[ord[j]] == tmp[ord[j + 1]]){
merge((ord[j] - 1) * m + i, (ord[j + 1] - 1) * m + i);
}
}
}
for(int i = 1; i <= n * m; i++){
int f = find(i);
if(!id[f]) id[f] = ++sz;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
tmp[j] = a[(i - 1) * m + j];
ord[j] = j;
}
sort(ord + 1, ord + 1 + m, cmp);
for(int j = 1; j < m; j++){
if(tmp[ord[j]] < tmp[ord[j + 1]]){
G[id[find((i - 1) * m + ord[j])]].emplace_back(id[find((i - 1) * m + ord[j + 1])]);
deg[id[find((i - 1) * m + ord[j + 1])]]++;
}
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
tmp[j] = a[(j - 1) * m + i];
ord[j] = j;
}
sort(ord + 1, ord + 1 + n, cmp);
for(int j = 1; j < n; j++){
if(tmp[ord[j]] < tmp[ord[j + 1]]){
G[id[find((ord[j] - 1) * m + i)]].emplace_back(id[find((ord[j + 1] - 1) * m + i)]);
deg[id[find((ord[j + 1] - 1) * m + i)]]++;
}
}
}
int res = 0;
queue<int> q;
for(int i = 1; i <= sz; i++)if(!deg[i]) q.emplace(i), ans[i] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
for(auto &v : G[u]){
deg[v]--;
ans[v] = max(ans[v], ans[u] + 1);
if(!deg[v]) q.emplace(v);
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout << res + ans[id[find((i - 1) * m + j)]] << (j == m ? 'n' : ' ');
}
}
return 0;
}
|
近期评论