Advertisement
Guest User

Untitled

a guest
May 16th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.57 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement