Advertisement
Saleh127

UVA 793 / DSU

Nov 20th, 2021
702
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-20-21.25.30
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. vector<ll>parent(200005),rankk(200005);
  13.  
  14. void make_set(ll n)
  15. {
  16.     for(ll i=0; i<=n+5; i++)
  17.     {
  18.         parent[i] = i;
  19.         rankk[i] = 0;
  20.     }
  21. }
  22.  
  23. ll find_set(ll v)
  24. {
  25.     if (v == parent[v])
  26.     {
  27.         return v;
  28.     }
  29.     return parent[v] = find_set(parent[v]);
  30. }
  31.  
  32. void union_sets(ll a, ll b)
  33. {
  34.     a = find_set(a);
  35.     b = find_set(b);
  36.  
  37.     if (a != b)
  38.     {
  39.         if (rankk[a] < rankk[b])
  40.         {
  41.             swap(a, b);
  42.         }
  43.  
  44.         parent[b] = a;
  45.  
  46.         if (rankk[a] == rankk[b])
  47.         {
  48.             rankk[a]++;
  49.         }
  50.     }
  51. }
  52.  
  53. int main()
  54. {
  55.    ios_base::sync_with_stdio(0);
  56.    cin.tie(0);cout.tie(0);
  57.  
  58.  
  59.    test
  60.    {
  61.         ll n,m,i,j,k=0,l=0,u,v;
  62.         string x;
  63.  
  64.         char c;
  65.  
  66.         cin>>n;
  67.  
  68.         make_set(n+2);
  69.  
  70.         cin.ignore();
  71.  
  72.         while(getline(cin,x) && x.size())
  73.         {
  74.              stringstream ss(x);
  75.  
  76.              ss>>c>>u>>v;
  77.  
  78.              if(c=='c')
  79.              {
  80.                   union_sets(u,v);
  81.              }
  82.              else
  83.              {
  84.                   if(find_set(u)==find_set(v))
  85.                   {
  86.                        k++;
  87.                   }
  88.                   else l++;
  89.              }
  90.         }
  91.  
  92.         cout<<k<<","<<l<<endl;
  93.  
  94.         if(cs!=tt) cout<<endl;
  95.  
  96.    }
  97.  
  98.  
  99.    get_lost_idiot;
  100. }
  101.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement