fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define p pair<int,int>
  4. #define f first
  5. #define s second
  6. typedef long long ll;
  7. using namespace std;
  8.  
  9. ll M = 1e9 + 7;
  10.  
  11. class DSU{
  12. 	public:
  13. 	vector<ll>sz;
  14. 	vector<int>par;
  15.    vector<int>blk; 
  16. 	DSU(int n){
  17. 		sz.resize(n+1,1ll);
  18. 		par.resize(n+1);
  19.         blk.resize(n+1,0);
  20. 		for(int i = 0;i<=n;i++) par[i] = i;
  21. 	}
  22. 	int findPar(int u){
  23. 		if(par[u] == u) return u;
  24. 		return par[u] = findPar(par[u]);
  25. 	}
  26.  
  27. 	void join(int u, int v){
  28. 		u = findPar(u); v = findPar(v);
  29. 		if(u == v) return;
  30. 		if(sz[u] > sz[v]) swap(u,v);
  31. 		sz[v] += sz[u];
  32.         blk[v] += blk[u]; 
  33. 		par[u] = v;
  34. 		return;
  35. 	}
  36. 	void update(int u, bool t){
  37.         u = findPar(u); 
  38.         if(t) blk[u]++;
  39.         else blk[u]--; 
  40.    } 
  41.    bool query(int u){
  42.         u = findPar(u); 
  43.         return (blk[u] > 0); 
  44.    }
  45. };
  46. int main() {
  47. 	ios_base::sync_with_stdio(false);
  48. 	cin.tie(NULL); cout.tie(NULL);
  49.  
  50. 	int n,q; cin>>n>>q;
  51. 	DSU dsu(n); 
  52.     vector<bool> state(n+1,1); 
  53. 	while(q--){
  54.        int t; cin>>t; 
  55.         if(t==1) {
  56. 	    	int u,v;cin>>u>>v;
  57. 	     	dsu.join(u,v);
  58.         } 
  59.        else if(t == 2){
  60.                int v; cin>>v; 
  61.                dsu.update(v,state[v]); 
  62.                state[v] = !state[v]; 
  63.         } 
  64.         else{
  65.              int v; cin>>v; 
  66.              if(dsu.query(v)) cout<<"Yes\n"; 
  67.              else cout<<"No\n"; 
  68.         }
  69.  
  70. 	}
  71.  
  72.  
  73. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
5 12
3 2
2 2
3 2
1 2 5
1 3 4
3 4
3 5
1 4 5
1 1 3
3 1
2 2
3 1
stdout
copy 
No
Yes
No
Yes
Yes
No
https://ideone.com/gLBXhw
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!