Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> p;
  6. vector<int> sz;
  7. vector< set<int> > s;
  8.  
  9. int get_par(int v){
  10. if(p[v]==v) return v;
  11. p[v] = get_par(p[v]);
  12. return p[v];
  13. }
  14.  
  15. void unite(int a, int b){
  16. a = get_par(a);
  17. b = get_par(b);
  18. if(a==b) return;
  19. if(sz[a]<sz[b]) swap(a,b);
  20. //a is par
  21. sz[a]+=sz[b];
  22. p[b] = a;
  23. if(s[a].size()<s[b].size()){
  24. swap(s[a],s[b]);
  25. }
  26. for(auto t:s[b]){
  27. int pt = get_par(t);
  28. s[pt].erase(b);
  29. s[pt].insert(a);
  30. s[a].insert(pt);
  31. }
  32. }
  33.  
  34. main(){
  35. ios::sync_with_stdio(false);
  36. cin.tie(0);
  37. int n,k;
  38. cin>>n>>k;
  39. sz.resize(n,1);
  40. s.resize(n,set<int>());
  41. p.resize(n);
  42. for(int i = 0; i < n; i++) p[i] = i;
  43.  
  44. for(int i = 0; i < k; i++){
  45. char c;
  46. int a,b;
  47. cin>>c>>a>>b;
  48. a--;b--;
  49. if(c=='+') unite(a,b);
  50. else if(c=='-'){
  51. a = get_par(a);
  52. b = get_par(b);
  53. s[b].insert(a);
  54. s[a].insert(b);
  55. }else{
  56. a = get_par(a);
  57. b = get_par(b);
  58. if(a==b){
  59. cout<<"+\n";
  60. }else if(s[a].find(b)!=s[a].end() || s[b].find(a)!=s[b].end()){
  61. cout<<"-\n";
  62. }else{
  63. cout<<"?\n";
  64. }
  65. }
  66. }
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement