Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, k, s[100001], p[100001], s1[100001], p1[100001], a, b;
  6. char h;
  7.  
  8. int f(int x)
  9. {
  10. int g = x;
  11. while (p[g] != g)
  12. g = p[g];
  13. return g;
  14. }
  15.  
  16. int f1(int x)
  17. {
  18. int g = x;
  19. while (p1[g] != g)
  20. g = p1[g];
  21. return g;
  22. }
  23.  
  24. int main()
  25. {
  26. iostream::sync_with_stdio(0); cin.tie(0);
  27. cin >> n >> k;
  28. for (int i = 1 ; i <= n ; i++)
  29. {
  30. s[i] = 1;
  31. p[i] = i;
  32. s1[i] = 1;
  33. p1[i] = i;
  34. }
  35. for (int xx = 0 ; xx < k ; xx++)
  36. {
  37. cin >> h >> a >> b;
  38. int a1 = a, b1 = b;
  39. if (h == '+')
  40. {
  41. a = f(a);
  42. b = f(b);
  43. if (a != b)
  44. {
  45. if (s[a] < s[b])
  46. swap(a, b);
  47. s[a] += s[b];
  48. p[b] = a;
  49. }
  50. a1 = f1(a1);
  51. b1 = f1(b1);
  52. if (a1 == b1)
  53. continue;
  54. if (s1[a1] < s1[b1])
  55. swap(a1, b1);
  56. s1[a1] += s1[b1];
  57. p1[b1] = a1;
  58. }
  59. else if (h == '-')
  60. {
  61. a1 = f1(a1);
  62. b1 = f1(b1);
  63. if (a1 == b1)
  64. continue;
  65. if (s1[a1] < s1[b1])
  66. swap(a1, b1);
  67. s1[a1] += s1[b1];
  68. p1[b1] = a1;
  69. }
  70. else
  71. {
  72. a = f(a);
  73. b = f(b);
  74. if (a == b)
  75. cout << "+\n";
  76. else
  77. {
  78. a1 = f1(a1);
  79. b1 = f1(b1);
  80. if (a1 == b1)
  81. cout << "-\n";
  82. else
  83. cout << "?\n";
  84. }
  85. }
  86. }
  87. return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement