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

解法：
考慮如果矩陣裡的數值全部相異，那麼問題很簡單，只要從最小的數值開始決定，由 1 開始賦值即可。那麼有一樣的有什麼影響呢？考慮把同一行，同一列有一樣數值的格子建立關係，而有關係的格子統一起來為一群。那麼只要由小的值一個群一個群考慮，就和簡單版的問題是一樣的要領。一個群需被賦予的值為群裡所有格子對應的行與列中目前被賦予的值裡最大的 +1。

時間 / 空間複雜度：
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 ];
    }
  }
}