Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <string>
- #include <set>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <numeric>
- #include <random>
- #include <memory>
- #include <chrono>
- #include <iterator>
- #include <functional>
- #include <unordered_set>
- #include <cassert>
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(x...)
- #endif
- //#pragma GCC optimize("Ofast")
- //#define int ll
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- #define mp make_pair
- #define pb push_back
- #define sz(x) int((x).size())
- #ifndef LOCAL
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(228);
- #endif
- const int N = 1e5 + 7;
- const int inf = INT_MAX / 2;
- const ll INF = LLONG_MAX / 3;
- const int MOD = 1e9 + 7;
- const double eps = 1e-6;
- const string cars[] = {"🚗", "🚕", "🚙"};
- set < int > s[N];
- struct dsu {
- vector <int> p, rang;
- dsu(int n) {
- p.resize(n);
- iota(p.begin(), p.end(), 0);
- rang.resize(n);
- }
- dsu() {};
- int find(int x) {
- return (p[x] == x ? x : p[x] = find(p[x]));
- }
- void join(int x, int y) {
- int a = find(x);
- int b = find(y);
- if (a != b) {
- set < int > t;
- for (int x : s[a]) {
- s[x].erase(a);
- t.insert(x);
- }
- for (int x : s[b]) {
- s[x].erase(b);
- t.insert(x);
- }
- if (rang[a] <= rang[b]) {
- p[a] = b;
- if (rang[a] == rang[b]) {
- rang[b]++;
- }
- s[a] = t;
- for (int x : t) {
- s[x].insert(a);
- }
- }
- else {
- p[b] = a;
- s[b] = t;
- for (int x : t) {
- s[x].insert(b);
- }
- }
- }
- }
- void add(int v) {
- int t = p.size();
- for (int i = t; i < t + v; i++) {
- p.push_back(p.size());
- rang.push_back(0);
- }
- }
- } a(N);
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(4);
- ios::sync_with_stdio(false);
- cin.tie();
- cout.tie();
- int n, q;
- cin >> n >> q;
- while (q--) {
- char cc;
- int u, v;
- cin >> cc >> u >> v;
- if (cc == '+') {
- a.join(u, v);
- }
- else if (cc == '-') {
- s[a.find(u)].insert(a.find(v));
- s[a.find(v)].insert(a.find(u));
- }
- else {
- int q = a.find(u), w = a.find(v);
- if (q == w) {
- cout << "+\n";
- }
- else if (s[q].find(w) != s[q].end() || s[w].find(q) != s[w].end()) {
- cout << "-\n";
- }
- else {
- cout << "?\n";
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement