Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. const int N = 1e5 + 5;
  9.  
  10. int p[N], sz[N];
  11. set<int> s[N];
  12.  
  13. int get(int v) {
  14. if (p[v] == v)
  15. return v;
  16. return p[v] = get(p[v]);
  17. }
  18.  
  19. void merge(int i, int j) {
  20. i = get(i), j = get(j);
  21. if (s[i].size() < s[j].size())
  22. swap(i, j);
  23.  
  24. for (int x : s[j]) {
  25. s[i].insert(x);
  26. s[x].erase(j);
  27. s[x].insert(i);
  28. }
  29. s[j].clear();
  30. p[j] = i;
  31. }
  32.  
  33. signed main() {
  34. for (int i = 0; i < N; ++i)
  35. p[i] = i, sz[i] = 1;
  36.  
  37. int n, k;
  38. cin >> n >> k;
  39. while (k--) {
  40. char sy;
  41. cin >> sy;
  42. int i, j;
  43. cin >> i >> j;
  44. --i, --j;
  45. if (sy == '+') {
  46. merge(i, j);
  47. } else if (sy == '-') {
  48. i = get(i), j = get(j);
  49. s[i].insert(j);
  50. s[j].insert(i);
  51. } else {
  52. if (get(i) == get(j)) {
  53. cout << "+\n";
  54. } else if (s[get(i)].count(get(j))) {
  55. cout << "-\n";
  56. } else {
  57. cout << "?\n";
  58. }
  59. }
  60. }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement