fork(2) download
  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
stdin
1
3
ab bc
sd ab
cd bc
stdout
2
3
4