Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pt pair<int, int>
- #define x first
- #define y second
- #define what_is(x) cerr << #x << " is " << x << endl;
- #define endl '\n'
- #define int long long
- #define ld long double
- const int N = 1e5 + 5;
- set<int> g[N];
- struct DSU
- {
- int rnk[N], parent[N];
- DSU ()
- {
- for (int i = 0; i < N; ++i)
- make_set(i);
- }
- void make_set(int v)
- {
- rnk[v] = 1;
- parent[v] = v;
- }
- int find_set(int v)
- {
- if (parent[v] == v)
- return v;
- return parent[v] = find_set(parent[v]);
- }
- void union_sets(int a, int b)
- {
- a = find_set(a);
- b = find_set(b);
- if (a != b)
- {
- if (rnk[a] < rnk[b]) swap(a, b);
- parent[b] = a;
- if (rnk[a] == rnk[b])
- ++rnk[a];
- for (auto i: g[b])
- g[a].insert(i);
- }
- }
- };
- DSU pos;
- bool check(int a, int b)
- {
- a = pos.find_set(a);
- b = pos.find_set(b);
- if (g[a].size() > g[b].size()) swap(a, b);
- for (auto i: g[a])
- if (pos.find_set(i) == b)
- return 1;
- for (auto i: g[b])
- if (pos.find_set(i) == a)
- return 1;
- return 0;
- }
- signed main()
- {
- cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
- int n, q;
- cin >> n >> q;
- while (q--)
- {
- char c;
- int a, b;
- cin >> c >> a >> b;
- if (c == '+') pos.union_sets(a, b);
- if (c == '-')
- {
- // neg.insert({pos.find_set(a), pos.find_set(b)});
- // neg.insert({pos.find_set(b), pos.find_set(a)});
- g[pos.find_set(a)].insert(pos.find_set(b));
- g[pos.find_set(b)].insert(pos.find_set(a));
- }
- if (c == '?')
- {
- if (pos.find_set(a) == pos.find_set(b))
- cout << "+" << endl;
- else if (check(a, b))
- cout << "-" << endl;
- else
- cout << "?" << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement