Advertisement
Derga

Untitled

Mar 28th, 2024
908
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.13 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <tuple>
  4. #include <unordered_set>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. struct Bridge {
  10.     Bridge(int node1, int node2) : node1_(min(node1, node2)), node2_(max(node1, node2)) {}
  11.     int node1_;
  12.     int node2_;
  13. };
  14.  
  15. bool operator==(const Bridge& lhs, const Bridge& rhs) {
  16.     return lhs.node1_ == rhs.node1_ && lhs.node2_ == rhs.node2_;
  17. }
  18.  
  19. class Dsu {
  20. public:
  21.     Dsu(int size) : parents(size) {
  22.         for (int i = 0; i < parents.size(); ++i) {
  23.             parents[i] = -1;
  24.         }
  25.     }
  26.  
  27.     bool IsInSameComponent(int u, int v) { return Parent(u) == Parent(v); }
  28.  
  29.     int Parent(int idx) {
  30.         if (parents[idx] < 0)
  31.             return idx;
  32.         return parents[idx] = Parent(parents[idx]);
  33.     }
  34.  
  35.     void Union(int u, int v) {
  36.         if (IsInSameComponent(u, v))
  37.             return;
  38.  
  39.         int pu = Parent(u);
  40.         int pv = Parent(v);
  41.         if (parents[pu] > parents[pv])
  42.             swap(pu, pv);
  43.         parents[pu] += parents[pv];
  44.         parents[pv] = pu;
  45.     }
  46.  
  47. private:
  48.     vector<int> parents;
  49. };
  50.  
  51. void Dfs(const vector<vector<int>>& edges, vector<bool>& is_visited,
  52.     unordered_set<Bridge>& result, int node1, int parent, int& time, vector<int>& enter, vector<int>& ret) {
  53.     is_visited[node1] = true;
  54.     time++;
  55.     enter[node1] = time;
  56.     ret[node1] = time;
  57.     for (int node2 : edges[node1]) {
  58.         if (node2 == parent) continue;
  59.         if (is_visited[node2]) {
  60.             ret[node1] = min(ret[node1], enter[node2]);
  61.             continue;
  62.         }
  63.         Dfs(edges, is_visited, result, node2, node1, time, enter, ret);
  64.         ret[node1] = min(ret[node1], ret[node2]);
  65.         if (enter[node1] >= ret[node2]) continue;
  66.         result.insert({ node1, node2 });
  67.     }
  68. }
  69.  
  70. int main() {
  71.     ios::sync_with_stdio(0);
  72.     cin.tie(0);
  73.  
  74.     int nodes_count, edges_count, requests_count;
  75.     cin >> nodes_count >> edges_count >> requests_count;
  76.     vector<vector<int>> edges(1 + nodes_count);
  77.     for (int i = 0; i < edges_count; ++i) {
  78.         int node1, node2;
  79.         cin >> node1 >> node2;
  80.         edges[node1].push_back(node2);
  81.         edges[node2].push_back(node1);
  82.     }
  83.  
  84.     vector<bool> is_visited(1 + nodes_count, false);
  85.     vector<int> enter(1 + nodes_count);
  86.     vector<int> ret(1 + nodes_count);
  87.     unordered_set<Bridge> result;
  88.     int time = 0;
  89.     for (int i = 1; i < is_visited.size(); ++i) {
  90.         if (is_visited[i]) continue;
  91.         Dfs(edges, is_visited, result, i, -1, time, enter, ret);
  92.     }
  93.  
  94.     Dsu dsu(nodes_count + 1);
  95.     for (int u = 0; u < edges.size(); ++u) {
  96.         for (auto v : edges[u]) {
  97.             if (result.count({ u, v }) || result.count({ v, u })) continue;
  98.  
  99.             dsu.Union(u, v);
  100.         }
  101.     }
  102.  
  103.     for (int i = 0; i < requests_count; ++i) {
  104.         int u, v;
  105.         cin >> u >> v;
  106.         if (dsu.IsInSameComponent(u, v)) {
  107.             cout << "YES\n";
  108.         }
  109.         else {
  110.             cout << "NO\n";
  111.         }
  112.     }
  113.     return 0;
  114. }
  115. /*
  116. test1
  117. 5 7 5
  118. 0 2
  119. 0 3
  120. 0 4
  121. 0 5
  122. 1 2
  123. 2 3
  124. 2 5
  125. 0 2
  126. 4 5
  127. 1 3
  128. 2 4
  129. 2 5
  130.  
  131. YES
  132. NO
  133. NO
  134. NO
  135. YES
  136. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement