fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int rankof[200005];
  6. int parent[200005];
  7.  
  8. void init(int n)
  9. {
  10.     for(int i=1; i<=n; i++)
  11.         { parent[i] = i; rankof[i] = 1; }
  12. }
  13.  
  14. int findnode(int x)
  15. {
  16.     if(parent[x]!=x)
  17.         parent[x] = findnode(parent[x]);
  18.     return parent[x];
  19. }
  20.  
  21. int main()
  22. {
  23.     int test;
  24.     scanf("%d",&test);
  25.     while(test--)
  26.     {
  27.         int N;
  28.         scanf("%d",&N);
  29.         int id = 1; string a, b;
  30.         map<string, int>mymap;
  31.         mymap.clear();
  32.         init(N*2);
  33.         for(int i=1; i<=N; i++)
  34.         {
  35.             cin>>a>>b;
  36.             if(!mymap[a])
  37.                 mymap[a] = id++;
  38.             if(!mymap[b])
  39.                 mymap[b] = id++;
  40.             int u = findnode(mymap[a]);
  41.             int v = findnode(mymap[b]);
  42.             if(u!=v)
  43.             {
  44.                 rankof[u] = rankof[v] + rankof[u];
  45.                 parent[v] = parent[u];
  46.             }
  47.             printf("%d\n",rankof[u]);
  48.         }
  49.     }
  50.     return 0;
  51. }
  52.  
Success #stdin #stdout 0s 4984KB
comments (?)
stdin
copy 
1
3
ab bc
sd ab
cd bc
stdout
copy 
2
3
4
https://ideone.com/34YqH9
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!