Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> p;
- vector<int> sz;
- vector< set<int> > s;
- int get_par(int v){
- if(p[v]==v) return v;
- p[v] = get_par(p[v]);
- return p[v];
- }
- void unite(int a, int b){
- a = get_par(a);
- b = get_par(b);
- if(a==b) return;
- if(sz[a]<sz[b]) swap(a,b);
- //a is par
- sz[a]+=sz[b];
- p[b] = a;
- if(s[a].size()<s[b].size()){
- swap(s[a],s[b]);
- }
- for(auto t:s[b]){
- int pt = get_par(t);
- s[pt].erase(b);
- s[pt].insert(a);
- s[a].insert(pt);
- }
- }
- main(){
- ios::sync_with_stdio(false);
- cin.tie(0);
- int n,k;
- cin>>n>>k;
- sz.resize(n,1);
- s.resize(n,set<int>());
- p.resize(n);
- for(int i = 0; i < n; i++) p[i] = i;
- for(int i = 0; i < k; i++){
- char c;
- int a,b;
- cin>>c>>a>>b;
- a--;b--;
- if(c=='+') unite(a,b);
- else if(c=='-'){
- a = get_par(a);
- b = get_par(b);
- s[b].insert(a);
- s[a].insert(b);
- }else{
- a = get_par(a);
- b = get_par(b);
- if(a==b){
- cout<<"+\n";
- }else if(s[a].find(b)!=s[a].end() || s[b].find(a)!=s[b].end()){
- cout<<"-\n";
- }else{
- cout<<"?\n";
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement