Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pt pair<int, int>
  6. #define x first
  7. #define y second
  8. #define what_is(x) cerr << #x << " is " << x << endl;
  9. #define endl '\n'
  10. #define int long long
  11. #define ld long double
  12.  
  13. const int N = 1e5 + 5;
  14.  
  15. set<int> g[N];
  16.  
  17. struct DSU
  18. {
  19. int rnk[N], parent[N];
  20.  
  21. DSU ()
  22. {
  23. for (int i = 0; i < N; ++i)
  24. make_set(i);
  25. }
  26.  
  27. void make_set(int v)
  28. {
  29. rnk[v] = 1;
  30. parent[v] = v;
  31. }
  32.  
  33. int find_set(int v)
  34. {
  35. if (parent[v] == v)
  36. return v;
  37. return parent[v] = find_set(parent[v]);
  38. }
  39.  
  40. void union_sets(int a, int b)
  41. {
  42. a = find_set(a);
  43. b = find_set(b);
  44. if (a != b)
  45. {
  46. if (rnk[a] < rnk[b]) swap(a, b);
  47. parent[b] = a;
  48. if (rnk[a] == rnk[b])
  49. ++rnk[a];
  50. for (auto i: g[b])
  51. g[a].insert(i);
  52. }
  53. }
  54. };
  55.  
  56. DSU pos;
  57.  
  58. bool check(int a, int b)
  59. {
  60. a = pos.find_set(a);
  61. b = pos.find_set(b);
  62. if (g[a].size() > g[b].size()) swap(a, b);
  63. for (auto i: g[a])
  64. if (pos.find_set(i) == b)
  65. return 1;
  66. for (auto i: g[b])
  67. if (pos.find_set(i) == a)
  68. return 1;
  69. return 0;
  70. }
  71.  
  72. signed main()
  73. {
  74. cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
  75.  
  76. int n, q;
  77. cin >> n >> q;
  78. while (q--)
  79. {
  80. char c;
  81. int a, b;
  82. cin >> c >> a >> b;
  83. if (c == '+') pos.union_sets(a, b);
  84. if (c == '-')
  85. {
  86. // neg.insert({pos.find_set(a), pos.find_set(b)});
  87. // neg.insert({pos.find_set(b), pos.find_set(a)});
  88. g[pos.find_set(a)].insert(pos.find_set(b));
  89. g[pos.find_set(b)].insert(pos.find_set(a));
  90. }
  91.  
  92. if (c == '?')
  93. {
  94. if (pos.find_set(a) == pos.find_set(b))
  95. cout << "+" << endl;
  96. else if (check(a, b))
  97. cout << "-" << endl;
  98. else
  99. cout << "?" << endl;
  100. }
  101. }
  102.  
  103. return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement