fork download
copy 
  1. /*
  2. *   author: kartik8800
  3. */
  4.  
  5. #include<bits/stdc++.h>
  6. #define ll long long
  7. #define pb push_back
  8. #define fr(a,b) for(int i = a; i < b; i++)
  9. #define rep(i,a,b) for(int i = a; i < b; i++)
  10. #define mod 1000000007
  11. #define inf (1LL<<60)`
  12. #define all(x) (x).begin(), (x).end()
  13. #define prDouble(x) cout << fixed << setprecision(10) << x
  14. #define triplet pair<ll,pair<ll,ll>>
  15. #define goog(tno) cout << "Case #" << tno++ <<": "
  16. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  17. #define read(x) int x; cin >> x
  18. using namespace std;
  19.  
  20. template <class T>
  21. class DisjointSetDS{
  22.   unordered_map<T, T> parent;
  23.   // set repr to <set size, set rank> 
  24.   unordered_map<T, pair<int, int>> representativeToSetSpecs;
  25. public:
  26.   void makeSet(T e){
  27.     parent[e] = e;
  28.     representativeToSetSpecs[e] = {1, 0};
  29.   }
  30.  
  31.   void unionSet(T e1, T e2) {
  32.     T repE1 = find(e1);
  33.     T repE2 = find(e2);
  34.  
  35.     if(repE1 == repE2){
  36.       return;
  37.     }
  38.  
  39.     int rankS1 = representativeToSetSpecs[repE1].second;
  40.     int rankS2 = representativeToSetSpecs[repE2].second;
  41.  
  42.     if(rankS1 > rankS2){
  43.       parent[repE2] = repE1;
  44.       representativeToSetSpecs[repE1].first += 
  45.               representativeToSetSpecs[repE2].first;
  46.       representativeToSetSpecs.erase(repE2);
  47.     }
  48.  
  49.     else {
  50.       parent[repE1] = repE2;
  51.       representativeToSetSpecs[repE2].first += 
  52.               representativeToSetSpecs[repE1].first;
  53.       if(rankS1 == rankS2)
  54.         representativeToSetSpecs[repE2].second++;
  55.       representativeToSetSpecs.erase(repE1);
  56.     }
  57.   }
  58.  
  59.   T find(T e) {
  60.     if(parent[e] == e)
  61.       return e;
  62.     return parent[e] = find(parent[e]);
  63.   }
  64.  
  65.   int sizeOfSet(T e){
  66.     T rep = find(e);
  67.     return representativeToSetSpecs[rep].first;
  68.   }
  69. };
  70.  
  71. int main() {
  72.    read(t);
  73.    while(t--){
  74.      read(n);
  75.      DisjointSetDS<string> dsu;
  76.      unordered_set<string> friendSeenBefore;
  77.      for(int connect = 0; connect < n; connect++) {
  78.        string friend1, friend2;
  79.        cin >> friend1; cin >> friend2;
  80.        if(friendSeenBefore.find(friend1) == friendSeenBefore.end()){
  81.          dsu.makeSet(friend1);
  82.        }
  83.        if(friendSeenBefore.find(friend2) == friendSeenBefore.end()){
  84.          dsu.makeSet(friend2);
  85.        }
  86.        friendSeenBefore.insert(friend1);
  87.        friendSeenBefore.insert(friend2);
  88.        dsu.unionSet(friend1, friend2);
  89.        cout << dsu.sizeOfSet(friend1) << '\n';
  90.      }
  91.    }
  92. }
  93.  
Success #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Bdh2It
1
4
Lucy Patty
Patty Alice
Alice Mira
Tiffany Jayden
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!