codeforces 650C

  1 #include <cstdio>
  2 #include <queue>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <map>
  9 #include <set>
 10 #include <ctime>
 11 #include <cmath>
 12 #include <cctype>
 13 #define N 1000010
 14 #define LL long long
 15 #define U unsigned
 16 using namespace std;
 17 int cas=1,T;
 18 int n,m,a[N],x[N],y[N];            //x储存第i行最大值，y储存第i列最大值
 19 struct node
 20 {
 21     int x,y,w;
 22     bool operator<(const node&a)const
 23     {
 24         return w<a.w;
 25     }
 26 };
 27 struct node1
 28 {
 29     int i,lx,ly,w;
 30     bool operator<(const node&a)const
 31     {
 32         return w>a.w;
 33     }
 34 };
 35 node e[N];
 36 int find(int x,map<int,int>&pa)
 37 {
 38     return pa[x]==x?x:pa[x]=find(pa[x],pa);
 39 }
 40 int main()
 41 {
 42     //freopen("1.in","w",stdout);
 43     //freopen("1.in","r",stdin);
 44     //freopen("1.out","w",stdout);
 45     //scanf("%d",&T);
 46     scanf("%d%d",&n,&m);
 47     for(int i=0;i<n;i++)
 48     {
 49         for(int j=0;j<m;j++)
 50         {
 51             int idx=i*m+j;
 52             scanf("%d",&e[idx].w);
 53             e[idx].x=i;
 54             e[idx].y=j;
 55         }
 56     }
 57     sort(e,e+n*m);        //排序后从小到大构建
 58     //for(int i=0;i<n*m;i++) printf("%d ",e[i].w);printf("
");
 59     //puts("ok");
 60     int i=0,end=n*m;
 61     while(i<end)
 62     {
 63         int l=i,r;
 64         for(r=i+1;e[l].w==e[r].w;r++);        //找出相等的所有数，再将相等的数分集，同一行或同一列会在同一集合
 65         //printf("lr:%d %d
",l,r);
 66         map<int,int>pa;        //二维并查集，first是原来的点，second是上一个点
 67         for(int j=l;j<r;j++)
 68         {
 69             pa.insert(make_pair(e[j].x,e[j].x));
 70             pa.insert(make_pair(e[j].y+N,e[j].x));
 71             int xx=find(e[j].x,pa);
 72             int yy=find(e[j].y+N,pa);
 73             if(xx!=yy) pa[yy]=xx;
 74         }
 75         map<int,int>val;
 76         for(int j=l;j<r;j++)
 77         {
 78             int minv=0;
 79             minv=max(x[e[j].x],y[e[j].y]);
 80             minv++;
 81             int xx=find(e[j].x,pa);
 82             val[xx]=max(val[xx],minv);
 83         }
 84         for(int j=l;j<r;j++)
 85         {
 86             int idx=e[j].x*m+e[j].y;
 87             a[idx]=val[find(e[j].x,pa)];
 88             x[e[j].x]=a[idx];
 89             y[e[j].y]=a[idx];
 90         }
 91         i=r;
 92     }
 93     //puts("ok");
 94     for(int i=0;i<n;i++)
 95     {
 96         for(int j=0;j<m;j++)
 97         {
 98             int idx=i*m+j;
 99             printf("%d%c",a[idx],j==m-1?'
':' ');
100         }
101     }
102     //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
103     return 0;
104 }
View Code