Advertisement
MegaVerkruzo

Untitled

Oct 30th, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <unordered_map>
  5. #include <string>
  6. #include <ctime>
  7.  
  8. using namespace std;
  9.  
  10. vector<pair<int, int>> pred;
  11.  
  12. int get_up(int u) {
  13. if (u == pred[u].first) {
  14. return u;
  15. }
  16. return pred[u].first = get_up(pred[u].first);
  17. }
  18.  
  19. void Union(int u, int v) {
  20. u = get_up(u);
  21. v = get_up(v);
  22. if (u == v) {
  23. return;
  24. }
  25. if (pred[u].second > pred[v].second) {
  26. pred[v].first = u;
  27. pred[u].second += pred[v].second;
  28. } else {
  29. pred[u].first = v;
  30. pred[v].second += pred[u].second;
  31. }
  32. }
  33.  
  34. bool check(int u, int v) {
  35. u = get_up(u);
  36. v = get_up(v);
  37. return u == v;
  38. }
  39.  
  40. int main() {
  41. unsigned int start = clock();
  42. vector<int> ansd;
  43. freopen("30", "r", stdin);
  44. int n, m, k;
  45. cin >> n >> m >> k;
  46. pred.resize(n + 1);
  47. for (int i = 1; i <= n; ++i) {
  48. pred[i].first = i;
  49. pred[i].second = 1;
  50. }
  51. vector<unordered_map<int, int>> g(n + 1);
  52. for (int i = 0; i < m; ++i) {
  53. int x, y;
  54. cin >> x >> y;
  55. g[x][y] = 1;
  56. g[y][x] = 1;
  57. }
  58. for (int i = 0; i < k; ++i) {
  59. int x, y;
  60. cin >> x >> y;
  61. Union(x, y);
  62. }
  63. vector<int> ans(n + 1, 0);
  64. for (int i = 1; i <= n; ++i) {
  65. vector<int> del;
  66. for (auto next : g[i]) {
  67. if (check(next.first, i)) {
  68. del.push_back(next.first);
  69. ans[i]++;
  70. }
  71. }
  72. for (int l = 0; l < del.size(); ++l) {
  73. g[i].erase(del[l]);
  74. }
  75. }
  76. int q;
  77. cin >> q;
  78. for (int i = 0; i < q; ++i) {
  79. char c;
  80. cin >> c;
  81. if (c == '?') {
  82. int x;
  83. cin >> x;
  84. ansd.push_back(ans[x]);
  85. } else {
  86. int x, y;
  87. cin >> x >> y;
  88. if (c == 'F') {
  89.  
  90. } else {
  91. if (!check(x, y)) {
  92. if (pred[x].second > pred[y].second) {
  93.  
  94. }
  95. Union(x, y);
  96. }
  97. }
  98. }
  99. }
  100. freopen("30.a", "r", stdin);
  101. for (int i = 0; i < ansd.size(); ++i) {
  102. int x;
  103. cin >> x;
  104. if (x != ansd[i]) {
  105. cout << "NO";
  106. }
  107. }
  108. cout << (clock() - start) / 1000.0;
  109. return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement