fork(1) 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; 
  30.         char a[21], b[21];
  31.         map<string, int>mymap;
  32.         mymap.clear();
  33.         init(N*2);
  34.         for(int i=1; i<=N; i++)
  35.         {
  36.             scanf("%s %s", a, b);
  37.             if(!mymap[a])
  38.                 mymap[a] = id++;
  39.             if(!mymap[b])
  40.                 mymap[b] = id++;
  41.             int u = findnode(mymap[a]);
  42.             int v = findnode(mymap[b]);
  43.             if(u!=v)
  44.             {
  45.                 rankof[u] = rankof[v] + rankof[u];
  46.                 parent[v] = parent[u];
  47.             }
  48.             printf("%d\n",rankof[u]);
  49.         }
  50.     }
  51.     return 0;
  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/MXXktl
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!