Samkit5025

Untitled

Aug 13th, 2022
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> par(500005);
  5. vector<int> ran(500005);
  6. vector<int> gro(500005);
  7.  
  8. void makeset(int n){
  9.     for(int i=1;i<=n;i++){
  10.         par[i] =i;
  11.         ran[i] =0;
  12.         gro[i] =1;
  13.     }
  14. }
  15.  
  16. int findPar(int i){
  17.     if(i == par[i]) return i;
  18.     return par[i] = findPar(par[i]);
  19. }
  20.  
  21. void uni(int a,int b){
  22.     a = findPar(a);
  23.     b = findPar(b);
  24.  
  25.     if(a==b){
  26.         return;
  27.     }
  28.     if(ran[a] < ran[b]){
  29.         gro[b]+=gro[a];
  30.         par[a] = b;
  31.     }
  32.     else if(ran[b] < ran[a]){
  33.         gro[a]+=gro[b];
  34.         par[b] = a;
  35.     }
  36.     else{
  37.         if(a<b){
  38.             gro[a]+=gro[b];
  39.             par[b] = a;
  40.             ran[a]++;
  41.         }
  42.         else{
  43.             gro[b]+=gro[a];
  44.             par[a] = b;
  45.             ran[b]++;
  46.         }
  47.     }
  48. }
  49.  
  50. vector<int> peopleGettingNews(int n, int m, vector<vector<int>> &a){
  51.     makeset(n);
  52.     for(int i=0;i<m;i++){
  53.         int len = a[i][0];
  54.         if(len!=0){
  55.             int last=-1;
  56.             for(int j=1;j<=len;j++){
  57.                 if(last == -1){
  58.                     last = a[i][j];
  59.                 }
  60.                 else{
  61.                     uni(last,a[i][j]);
  62.                 }
  63.             }
  64.         }
  65.     }
  66.  
  67.     vector<int> res;
  68.     for(int i=1;i<=n;i++){
  69.         res.push_back(gro[findPar(i)]);
  70.     }
  71.     return res;
  72. }
  73.  
  74. signed main() {
  75.    
  76.     int n,m;
  77.     cin>>n>>m;
  78.  
  79.     vector<vector<int>> a(m);
  80.     for(int i=0;i<m;i++){
  81.         int size;
  82.         cin>>size;
  83.         a[i].push_back(size);
  84.         for(int j=0;j<size;j++){
  85.             int temp;
  86.             cin>>temp;
  87.             a[i].push_back(temp);
  88.         }
  89.     }
  90.  
  91.     vector<int> ans = peopleGettingNews(n,m,a);
  92.     for(int i=0;i<n;i++){
  93.         cout<<ans[i]<<" ";
  94.     }
  95.     cout<<endl;
  96. }
  97.  
Advertisement
Add Comment
Please, Sign In to add comment