Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <set>
- using namespace std;
- vector<int> parent;
- // тут должны быть только корни
- set<int> notExist[100001];
- int getParent(int v) {
- if (parent[v] == -1 or v == parent[v]) return v;
- int x = parent[v];
- while (parent[x] != -1 and parent[x] != x) x = parent[x];
- parent[v] = x;
- return x;
- }
- void unite(int id1, int id2) {
- if (notExist[id1].size() > notExist[id2].size()) swap(id1, id2);
- for (int i : notExist[getParent(id1)]) {
- notExist[getParent(id2)].insert(getParent(i));
- notExist[getParent(i)].insert(getParent(id2));
- }
- parent[getParent(id1)] = getParent(id2);
- }
- signed main() {
- int n, k;
- cin >> n >> k;
- parent.resize(n + 1, -1);
- for (int i = 0; i < k; ++i) {
- char op;
- int a, b;
- cin >> op >> a >> b;
- if (op == '+') {
- unite(a, b);
- } else if (op == '-') {
- notExist[getParent(a)].insert(getParent(b));
- notExist[getParent(b)].insert(getParent(a));
- } else if (op == '?') {
- if (getParent(a) == getParent(b)) cout << "+" << endl;
- else if (notExist[getParent(a)].find(getParent(b)) != notExist[getParent(a)].end())
- cout << "-" << endl;
- else cout << "?" << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement