fork download
copy 
  1.     #include<bits/stdc++.h>
  2.  
  3.     using namespace std;
  4.  
  5.     int rankof[800005];
  6.     int parent[800005];
  7.     string ht[800005];
  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 hash(char* s) {
  22.       int h = 1;
  23.       for (int i = 0; s[i]; i++) {
  24.         h = h * 23 + s[i];
  25.         h %= 600000;
  26.       }
  27.       while (ht[h] != "" && ht[h] != s) h++;
  28.       if (ht[h] == "") ht[h] = s;
  29.       return h;
  30.     }
  31.  
  32.  
  33.     int main()
  34.     {
  35.         int test;
  36.         scanf("%d",&test);
  37.         while(test--)
  38.         {
  39.             int N;
  40.             scanf("%d",&N);
  41.             int id = 1;
  42.             init(800000);
  43.             char a[21], b[21];
  44.             for(int i=1; i<=N; i++)
  45.             {
  46.                 scanf("%s %s", a, b);
  47.                 int u = findnode(hash(a));
  48.                 int v = findnode(hash(b));
  49.                 if(u!=v)
  50.                 {
  51.                     rankof[u] = rankof[v] + rankof[u];
  52.                     parent[v] = parent[u];
  53.                 }
  54.                 printf("%d\n",rankof[u]);
  55.             }
  56.         }
  57.         return 0;
  58.     }
  59.  
Success #stdin #stdout 0s 12832KB
comments (?)
stdin
copy 
1
3
ab bc
sd ab
cd bc
stdout
copy 
2
3
4
https://ideone.com/nROrJK
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!