Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. vector<int> parent;
  9.  
  10. // тут должны быть только корни
  11. set<int> notExist[100001];
  12.  
  13. int getParent(int v) {
  14.   if (parent[v] == -1 or v == parent[v]) return v;
  15.   int x = parent[v];
  16.   while (parent[x] != -1 and parent[x] != x) x = parent[x];
  17.   parent[v] = x;
  18.   return x;
  19. }
  20.  
  21. void unite(int id1, int id2) {
  22.   if (notExist[id1].size() > notExist[id2].size()) swap(id1, id2);
  23.   for (int i : notExist[getParent(id1)]) {
  24.     notExist[getParent(id2)].insert(getParent(i));
  25.     notExist[getParent(i)].insert(getParent(id2));
  26.   }
  27.   parent[getParent(id1)] = getParent(id2);
  28. }
  29.  
  30. signed main() {
  31.   int n, k;
  32.   cin >> n >> k;
  33.   parent.resize(n + 1, -1);
  34.   for (int i = 0; i < k; ++i) {
  35.     char op;
  36.     int a, b;
  37.     cin >> op >> a >> b;
  38.     if (op == '+') {
  39.       unite(a, b);
  40.     } else if (op == '-') {
  41.       notExist[getParent(a)].insert(getParent(b));
  42.       notExist[getParent(b)].insert(getParent(a));
  43.     } else if (op == '?') {
  44.       if (getParent(a) == getParent(b)) cout << "+" << endl;
  45.       else if (notExist[getParent(a)].find(getParent(b)) != notExist[getParent(a)].end())
  46.         cout << "-" << endl;
  47.       else cout << "?" << endl;
  48.     }
  49.   }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement