Advertisement
madhukeshk3

Compress 2-D array GOOGLE

Jul 27th, 2020
207
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pfin(a) printf("%d\n",a);
  5. #define pfis(a) printf("%d ",a);
  6. #define sfi(a) scanf("%d",&a);
  7. #define f(i,a,b) for(int i=a;i<b;i++)
  8. #define pb(a) push_back(a);
  9. #define vi vector<int>
  10.  
  11. struct util
  12. {
  13.     int val,node;
  14. };
  15.  
  16. bool cmp(util a,util b)
  17. {
  18.     return a.val<b.val;
  19. }
  20.  
  21. vi g[100005];
  22. int in[100005]={0};
  23. int ans[100005];
  24.  
  25. void toposort(int n)
  26. {
  27.     queue<int>q;
  28.     f(i,0,n)
  29.     {
  30.         if(in[i]==0)
  31.         {
  32.             q.push(i);
  33.             ans[i]=1;
  34.         }
  35.     }
  36.  
  37.     while(!q.empty())
  38.     {
  39.         int u=q.front();
  40.         q.pop();
  41.  
  42.         for(int i=0;i<g[u].size();i++)
  43.         {
  44.             int v=g[u][i];
  45.             in[v]--;
  46.             if(in[v]==0)
  47.             {
  48.                 ans[v]=ans[u]+1;
  49.                 q.push(v);
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55. int main()
  56. {
  57.     int r,c;
  58.     sfi(r)
  59.     sfi(c)
  60.  
  61.     util rows[r][c];
  62.     util cols[c][r];
  63.  
  64.     int mat[r][c];
  65.     f(i,0,r)
  66.     {
  67.         f(j,0,c)
  68.         {
  69.             sfi(mat[i][j]);
  70.             rows[i][j].val=mat[i][j];
  71.             rows[i][j].node=(i*c)+j;
  72.             cols[j][i].val=mat[i][j];
  73.             cols[j][i].node=(i*c)+j;
  74.         }
  75.     }
  76.  
  77.     f(i,0,r)
  78.         sort(rows[i],rows[i]+c,cmp);
  79.     f(i,0,c)
  80.         sort(cols[i],cols[i]+r,cmp);
  81.  
  82.     f(i,0,r)
  83.     {
  84.         f(j,0,c-1)
  85.         {
  86.             if(rows[i][j].val<rows[i][j+1].val)
  87.             {
  88.                 g[rows[i][j].node].pb(rows[i][j+1].node)
  89.                 in[rows[i][j+1].node]++;
  90.             }
  91.         }
  92.     }
  93.  
  94.     f(i,0,c)
  95.     {
  96.         f(j,0,r-1)
  97.         {
  98.             if(cols[i][j].val<cols[i][j+1].val)
  99.             {
  100.                 g[cols[i][j].node].pb(cols[i][j+1].node)
  101.                 in[cols[i][j+1].node]++;
  102.             }
  103.         }
  104.     }
  105.  
  106.     toposort(r*c);
  107.  
  108.     for(int i=0;i<r*c;i++)
  109.     {
  110.         pfis(ans[i])
  111.         if((i+1)%c==0)
  112.             printf("\n");
  113.     }
  114.  
  115.    return 0;
  116. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement