Codeforces Round #345 (Div. 1) C. Table Compression (并查集)

Little Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithmsand many others. Inspired by the new knowledge, Petya is now developing the new compression alg

Kirito_Acmer

873人浏览 · 2016-03-16 18:25:50

Kirito_Acmer · 2016-03-16 18:25:50 发布

Little Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.

Petya decided to compress tables. He is given a table a consisting of n rows and m columns that is filled with positive integers. He wants to build the table a' consisting of positive integers such that the relative order of the elements in each row and each column remains the same. That is, if in some row i of the initial table ai, j < ai, k, then in the resulting table a'i, j < a'i, k, and if ai, j = ai, k then a'i, j = a'i, k. Similarly, if in some column j of the initial table ai, j < ap, j then in compressed table a'i, j < a'p, j and if ai, j = ap, j then a'i, j = a'p, j.

Because large values require more space to store them, the maximum value in a' should be as small as possible.

Petya is good in theory, however, he needs your help to implement the algorithm.

Input

The first line of the input contains two integers n and m ( $\text{[math]}$ , 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 ≤ 109) that are the values in the table.

Output

Output the compressed table in form of n lines each containing m integers.

If there exist several answers such that the maximum number in the compressed table is minimum possible, you are allowed to output any of them.

   Examples 
 

     input 
   
2 2
1 2
3 4

     output 
   
1 2
2 3

     input 
   
4 3
20 10 30
50 40 30
50 60 70
90 80 70

     output 
   
2 1 3
5 4 3
5 6 7
9 8 7
题意：给你一个n*n的由数字组成的矩阵，让你尽量缩小这个矩阵中的值，使得缩小前后两个矩阵每一行每一列任意两个数对应的大小关系一致。
思路：先考虑所有的点对应的数都不同，那么我们只要对所有的数排个序，然后依次编号就行了，相当于一次离散化。那么现在给你的矩形是有相同元素的，可以观察到同一行或者同一列的数缩小后也是一样的，且它们最小能缩小到的数是符合它们各自所在行的之前算出来的最小数+1，我们可以用并查集把这些数都统一成一个数，然后就能算了。

<pre name="code" class="cpp">#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef long double ldb;
#define inf 99999999
#define pi acos(-1.0)
#define maxn 1000050
struct node{
    int x,y,num,idx;
}a[maxn];
bool cmp(node a,node b){
    return a.num<b.num;
}
int X[maxn],Y[maxn],x[maxn],y[maxn];


int ans[maxn];
int pre[maxn];

int findset(int x)
{
    int i=x,j,r=x;
    while(r!=pre[r]){
        r=pre[r];
    }
    while(i!=pre[i]){
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;

}


int main()
{
    int n,m,i,j,c,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int tot=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%d",&c);
                tot++;
                a[tot].x=i;a[tot].y=j;
                a[tot].idx=tot;a[tot].num=c;
                pre[tot]=tot;
            }
        }
        sort(a+1,a+1+tot,cmp);

        for(i=1;i<=tot;){
            for(j=i;a[i].num==a[j].num;j++);
            int r,c;
            for(k=i;k<j;k++){
                r=a[k].x;c=a[k].y;
                if(!x[r])x[r]=a[k].idx ;
                else{
                    pre[findset(a[k].idx ) ]=findset(x[r]);
                }
                if(!y[c])y[c]=a[k].idx ;
                else{
                    pre[findset(a[k].idx ) ]=findset(y[c]);
                }
            }
            for(k=i;k<j;k++){
                int q=findset(a[k].idx );
                int answer=max(X[a[k].x ],Y[a[k].y ] )+1;
                ans[q]=max(ans[q],answer );
            }
            for(k=i;k<j;k++){
                X[a[k].x ]=Y[a[k].y ]=ans[a[k].idx ]=ans[findset(a[k].idx ) ];
                x[a[k].x ]=y[a[k].y ]=0;
            }
            i=j;
        }
        int flag=1;


        for(i=1;i<=tot;i++){
            if(flag){
                flag=0;printf("%d",ans[i]);
            }
            else{
                printf(" %d",ans[i]);
            }
            if(i%m==0){
                flag=1;printf("\n");
            }
        }
    }
    return 0;
}