Advertisement
Saleh127

UVA 10158 / DSU

Nov 19th, 2021
1,110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-20-00.45.32
  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<=2*n+2; 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);
  57.     cout.tie(0);
  58.  
  59.     ll c,n,x,y,ex,ey;
  60.  
  61.  
  62.     cin>>n;
  63.  
  64.     make_set(n+5);
  65.  
  66.     while(cin>>c>>x>>y && (c+x+y))
  67.     {
  68.  
  69.         ex=find_set(x+n); ///consider enemy of x
  70.         ey=find_set(y+n); ///consider enemy of y
  71.         x=find_set(x);
  72.         y=find_set(y);
  73.  
  74.         if(c==1)
  75.         {
  76.             ///set
  77.             ///we r friend if your enemy is not my friend
  78.  
  79.             if(x==ey) cout<<-1<<nl;
  80.             else
  81.             {
  82.                 union_sets(x,y);
  83.                 union_sets(ex,ey);
  84.             }
  85.         }
  86.  
  87.         else if(c==2)
  88.         {
  89.             ///set
  90.             ///we r enemy if we r not friend
  91.  
  92.             if(x==y) cout<<-1<<nl;
  93.             else
  94.             {
  95.                 union_sets(x,ey);
  96.                 union_sets(ex,y);
  97.             }
  98.         }
  99.         else if(c==3)
  100.         {
  101.              ///check r we friend?
  102.  
  103.             if(x==y) cout<<1<<nl;
  104.             else cout<<0<<nl;
  105.         }
  106.         else
  107.         {
  108.             ///check r we enemy?
  109.             ///we r enemy if your enemy is my friend
  110.  
  111.             if(x==ey) cout<<1<<nl;
  112.             else cout<<0<<nl;
  113.         }
  114.     }
  115.  
  116.     get_lost_idiot;
  117. }
  118.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement