Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5.  
  6. using namespace std;
  7. typedef long long ll;
  8. typedef long double ld;
  9. typedef string str;
  10. const int N = 2e5 + 3, INF = 1e5;
  11.  
  12. int parent[N];
  13. ll sz[N];
  14. bool use[N];
  15.  
  16. int find_set(int v){
  17.     if(v == parent[v])
  18.         return v;
  19.     return parent[v] = find_set (parent[v]);
  20. }
  21.  
  22. void union_sets(int a, int b){
  23.     a = find_set(a);
  24.     b = find_set(b);
  25.     if(a != b){
  26.         if(sz[a] < sz[b])
  27.             swap (a, b);
  28.         parent[b] = a;
  29.         sz[a] += sz[b];
  30.     }
  31. }
  32.  
  33. int main()
  34. {
  35.     ios :: sync_with_stdio(0);
  36.     cin.tie(NULL), cout.tie(NULL);
  37.     //freopen("sum.in", "r", stdin), freopen("sum.out", "w", stdout);
  38.     int n, q;
  39.     map <pair <int, int>, bool> mp;
  40.     cin >> n >> q;
  41.     for(int i = 0; i < n; ++i) parent[i] = i, sz[i] = 1;
  42.     while(q--){
  43.         char c;
  44.         int a, b;
  45.         cin >> c >> a >> b;
  46.         if(c == '+') union_sets(a, b), use[a] = 1, use[b] = 1;
  47.         else if(c == '-'){
  48.             int pa = find_set(a), pb = find_set(b);
  49.             sz[pa] += INF, sz[pb] += INF
  50.         }
  51.     }
  52.  
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement