# CFR 650 C. Table Compression ( Union Find )

Problem - C - Codeforces

The first line of the input contains two integers n and m (, the number of rows and the number of columns of the table respectively.
Each of the following n rows contain m integers ai, j (1 ≤ ai, j ≤ 1e9) that are the values in the table.
TL: 4000 ms
ML: 256 MB

O( N * M * lg( N * M ) )

```int N, M;
vvi A;

void init(){
cin >> N >> M;
A = vvi( N, vi( M ) );
for( int i = 0; i < N; ++i ){
for( int j = 0; j < M; ++j ){
cin >> A[ i ][ j ];
}
}
}

struct dsu{
vi fa;
dsu( int size ){
fa = vi( size );
for( int i = 0; i < size; ++i ){
fa[ i ] = i;
}
}
int find( int x ){
if( fa[ x ] == x ) return x;
return fa[ x ] = find( fa[ x ] );
}
int unite( int x, int y ){
int a = find( x );
int b = find( y );
if( a == b ) return 0;
fa[ b ] = a;
return 1;
}
} *uf;

void preprocess(){
uf = new dsu( N * M );
for( int i = 0; i < N; ++i ){
vp val_id;
for( int j = 0; j < M; ++j ){
val_id.emplace_back( A[ i ][ j ], i * M + j );
}
sort( val_id.begin(), val_id.end() );
for( int j = 0; j + 1 < M; ++j ){
if( val_id[ j ].first != val_id[ j + 1 ].first ) continue;
uf->unite( val_id[ j ].second, val_id[ j + 1 ].second );
}
}
for( int i = 0; i < M; ++i ){
vp val_id;
for( int j = 0; j < N; ++j ){
val_id.emplace_back( A[ j ][ i ], j * M + i );
}
sort( val_id.begin(), val_id.end() );
for( int j = 0; j + 1 < N; ++j ){
if( val_id[ j ].first != val_id[ j + 1 ].first ) continue;
uf->unite( val_id[ j ].second, val_id[ j + 1 ].second );
}
}
}

void solve(){
vp val_id;
vvi depend( N * M );
for( int i = 0; i < N; ++i ){
for( int j = 0; j < M; ++j ){
if( uf->find( i * M + j ) == i * M + j ){
val_id.emplace_back( A[ i ][ j ], i * M + j );
} else{
depend[ uf->find( i * M + j ) ].emplace_back( i * M + j );
}
}
}
sort( val_id.begin(), val_id.end() );
vi row2max( N );
vi col2max( M );
vi depend2ans( N * M );
for( int i = 0; i < val_id.size(); ++i ){
int x = val_id[ i ].second / M;
int y = val_id[ i ].second % M;
int v = val_id[ i ].first;
int ans = max( { 1, row2max[ x ] + 1, col2max[ y ] + 1 } );
for( int j : depend[ uf->find( x * M + y ) ] ){
upmax( ans, row2max[ j / M ] + 1 );
upmax( ans, col2max[ j % M ] + 1 );
}
upmax( row2max[ x ], ans );
upmax( col2max[ y ], ans );
upmax( depend2ans[ uf->find( x * M + y ) ], ans );
for( int j : depend[ uf->find( x * M + y ) ] ){
upmax( row2max[ j / M ], ans );
upmax( col2max[ j % M ], ans );
}
}
for( int i = 0; i < N; ++i ){
for( int j = 0; j < M; ++j ){
cout << depend2ans[ uf->find( i * M + j ) ] << " \n"[ j + 1 == M ];
}
}
}
```