Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- using namespace std;
- const int N = 1e5 + 5;
- int p[N], sz[N];
- set<int> s[N];
- int get(int v) {
- if (p[v] == v)
- return v;
- return p[v] = get(p[v]);
- }
- void merge(int i, int j) {
- i = get(i), j = get(j);
- if (s[i].size() < s[j].size())
- swap(i, j);
- for (int x : s[j]) {
- s[i].insert(x);
- s[x].erase(j);
- s[x].insert(i);
- }
- s[j].clear();
- p[j] = i;
- }
- signed main() {
- for (int i = 0; i < N; ++i)
- p[i] = i, sz[i] = 1;
- int n, k;
- cin >> n >> k;
- while (k--) {
- char sy;
- cin >> sy;
- int i, j;
- cin >> i >> j;
- --i, --j;
- if (sy == '+') {
- merge(i, j);
- } else if (sy == '-') {
- i = get(i), j = get(j);
- s[i].insert(j);
- s[j].insert(i);
- } else {
- if (get(i) == get(j)) {
- cout << "+\n";
- } else if (s[get(i)].count(get(j))) {
- cout << "-\n";
- } else {
- cout << "?\n";
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement