Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, k, s[100001], p[100001], a, b;
- char h;
- set <pair <int, int>> r;
- int f(int x)
- {
- int g = x;
- while (p[g] != g)
- g = p[g];
- return g;
- }
- int main()
- {
- iostream::sync_with_stdio(0); cin.tie(0);
- cin >> n >> k;
- for (int i = 1 ; i <= n ; i++)
- {
- s[i] = 1;
- p[i] = i;
- }
- for (int xx = 0 ; xx < k ; xx++)
- {
- cin >> h >> a >> b;
- if (h == '+')
- {
- a = f(a);
- b = f(b);
- if (a != b)
- {
- if (s[a] < s[b])
- swap(a, b);
- s[a] += s[b];
- p[b] = a;
- }
- }
- else if (h == '-')
- {
- a = f(a);
- b = f(b);
- r.insert({a, b});
- }
- else
- {
- a = f(a);
- b = f(b);
- if (a == b)
- {
- cout << "+\n";
- continue;
- }
- if (a > b)
- swap(a, b);
- set <pair <int, int>> t;
- for (pair <int, int> g: r)
- {
- int i, j;
- tie(i, j) = g;
- i = f(i);
- j = f(j);
- if (i > j)
- swap(i, j);
- t.insert({i, j});
- }
- r.clear();
- int er = 0;
- for (pair <int, int> g: t)
- {
- r.insert(g);
- if (a == g.first && b == g.second)
- er++;
- }
- if (er)
- cout << "-\n";
- else
- cout << "?\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement