fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. map<string,string>parent;
  5. map<string,int>sz;
  6.  
  7. string Find(string u)
  8. {
  9.     if(parent[u] == u) return u;
  10.     return parent[u] = Find(parent[u]);
  11. }
  12.  
  13. void Union(string a,string b)
  14. {
  15.     parent[a] = b;
  16.     sz[a] += sz[b];
  17.     sz[b] = sz[a];
  18. }
  19. void solve()
  20. {
  21.     int n;
  22.     cin >> n;
  23.     for(int i = 0;i < n;i++)
  24.     {
  25.        string a,b;
  26.        cin >> a >> b;
  27.        if(parent[a] == "") {
  28.             parent[a] = a;
  29.             sz[a] = 1;
  30.        }
  31.        if(parent[b] == "") {
  32.             parent[b] = b; sz[b] = 1;
  33.        }
  34.  
  35.        string x = Find(a);
  36.        string y = Find(b);
  37.  
  38.        if(x != y)
  39.        {
  40.            Union(x,y);
  41.        }
  42.        //cout<<"parent : "<<parent[a]<<" "<<parent[b]<<endl;
  43.        cout<<sz[x]<<endl;
  44.  
  45.  
  46.     }
  47.     parent.clear();
  48.     sz.clear();
  49.  
  50. }
  51. int main()
  52. {
  53.     int t;
  54.     cin >> t;
  55.     while(t--)
  56.     {
  57.         solve();
  58.     }
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0s 5512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lX3fRf
problem FRNDCIRC, based on SPOJ submission 30057329 (CPP14-CLANG), 2022-09-18 11:26:43
language:
C++14 (clang 8.0)
created:
2 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!