SHARE
TWEET

Untitled

a guest May 16th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define pii              pair <int,int>
  3. #define pll              pair <long long,long long>
  4. #define sc               scanf
  5. #define pf               printf
  6. #define Pi               2*acos(0.0)
  7. #define ms(a,b)          memset(a, b, sizeof(a))
  8. #define pb(a)            push_back(a)
  9. #define MP               make_pair
  10. #define db               double
  11. #define ll               long long
  12. #define ull              unsigned long long
  13. #define f                first
  14. #define s                second
  15. #define sqr(x)           (x)*(x)
  16. #define VI               vector <int>
  17. #define DBG              pf("Hi\n")
  18. #define MOD              1000000007
  19. #define SZ(a)            (int)a.size()
  20. #define sf(a)            scanf("%d",&a)
  21. #define sfl(a)           scanf("%lld",&a)
  22. #define sff(a,b)         scanf("%d %d",&a,&b)
  23. #define sffl(a,b)        scanf("%lld %lld",&a,&b)
  24. #define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
  25. #define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
  26. #define loop(i,n)        for(int i=0;i<n;i++)
  27. #define loop1(i,n)       for(int i=1;i<=n;i++)
  28. #define REP(i,a,b)       for(int i=a;i<b;i++)
  29. #define RREP(i,a,b)      for(int i=a;i>=b;i--)
  30. #define intlim           2147483648
  31. #define ull              unsigned long long
  32. #define gcd(a, b)        __gcd(a, b)
  33. #define lcm(a, b)        ((a)*((b)/gcd(a,b)))
  34. #define mk(x1,y1) make_pair(x1, y1)
  35. #define maxl 500010
  36. #define psz 20
  37. using namespace std;
  38.  
  39. /*----------------------Graph Moves----------------*/
  40. //const int fx[]={+1,-1,+0,+0};
  41. //const int fy[]={+0,+0,+1,-1};
  42. //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
  43. //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
  44. //const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
  45. //const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
  46. /*------------------------------------------------*/
  47.  
  48. /*-----------------------Bitmask------------------*/
  49. //int Set(int N,int pos){return N=N | (1<<pos);}
  50. //int reset(int N,int pos){return N= N & ~(1<<pos);}
  51. //bool check(int N,int pos){return (bool)(N & (1<<pos));}
  52. //freopen("in.txt","r",stdin);
  53. //freopen("out.txt","w",stdin);
  54. //ios_base::sync_with_stdio(false);
  55.  //cin.tie(NULL);
  56.  
  57. int cnt=0,group[maxl],sz[maxl],cas=1;
  58. long long total=0;
  59.  
  60. int find_root(int i)
  61. {
  62.    // cout<<"E  "<<i<<"  "<<group[i]<<endl;
  63.     while( i != group[i] )
  64.     {
  65.         group[i]=group[group[i]];
  66.         i=group[i];
  67.     }
  68.     return i;
  69. }
  70.  
  71. int transfer_and_size(int ra, int rb)
  72. {
  73.     if(sz[ra]>=sz[rb])
  74.     {
  75.         sz[ra]+=sz[rb];
  76.         group[rb]=group[ra];
  77.     }
  78.     else
  79.     {
  80.         sz[rb]+=sz[ra];
  81.         group[ra]=group[rb];
  82.     }
  83.     // cout<<"W  "<<sz[ra]<<"  "<<sz[rb]<<endl;
  84. }
  85.  
  86.  
  87. int n,m;
  88.  
  89. void initialize(){
  90.  
  91.     for(int i=0; i<=n; i++) sz[i]=0, group[i] = i;
  92. }
  93.  
  94.  
  95. int main(){
  96.  
  97.     cin>>n>>m;
  98.  
  99.     initialize();
  100.  
  101.     //for(int i=1; i<=n; i++) cout<<"I  "<<find_root(i)<<endl;
  102.  
  103.     for(int i=0; i<m; i++){
  104.  
  105.         int k;
  106.         scanf("%d",&k);
  107.         int a[k+2];
  108.  
  109.         for(int i1=0; i1<k; i1++){
  110.  
  111.             scanf("%d",&a[i1]);
  112.  
  113.             int rr = find_root(a[i1]);
  114.  
  115.             if( rr == a[i1] && sz[rr] == 0){
  116.                 sz[rr]++;
  117.             }
  118.         }
  119.  
  120.         for (int j = 1; j < k; j++){
  121.  
  122.             int r1 = find_root(a[j-1]), r2 = find_root(a[j]);
  123.             if(r1 == r2 ) continue;
  124.  
  125.             transfer_and_size(r1,r2);        
  126.         }
  127.     }  
  128.  
  129.      for(int i=1; i<=n; i++){
  130.        // cout<<"T  "<<i<<"  "<<find_root(i)<<endl;
  131.         printf("%d ",max(1,sz[find_root(i)]));
  132.     }
  133.  
  134.     return 0;
  135. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top