Advertisement
sacr1ficerq

Articulation points

Apr 15th, 2022
31
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1. /* */
  2.  
  3. #include <vector>
  4. #include <iostream>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. class Graph {
  10. public:
  11.     explicit Graph(size_t v_amount) : graph(v_amount + 1), visited(v_amount + 1), tin(v_amount+1, v_amount+1),
  12.     up(v_amount+1, v_amount+1), from(v_amount + 1), children(v_amount+1){
  13.     }
  14.  
  15.     void add_e(size_t a, size_t b) {
  16.         graph[a].push_back(b);
  17.         graph[b].push_back(a);
  18.     }
  19.  
  20.     vector<size_t> get_articulation_points(){
  21.         time = 0;
  22.         for(size_t v = 1; v < graph.size(); ++v){
  23.             if (visited[v] == 0){
  24.                 dfs(v);
  25.                 if (children[v] < 2){
  26.                     art_points.erase(v);
  27.                 }
  28.             }
  29.         }
  30.         art_points.erase(0);
  31.         return {art_points.begin(), art_points.end()};
  32.     }
  33.  
  34.  
  35.     void dfs(size_t v){
  36.         visited[v] = 1;
  37.         ++time;
  38.         tin[v] = time;
  39.         for (auto neighbour : graph[v]){
  40.             if (visited[neighbour] == 0){
  41.                 from[neighbour] = v;
  42.                 children[v]++;
  43.                 dfs(neighbour);
  44.                 up[v] = min(up[v], up[neighbour]);
  45.                 if (up[neighbour] >= tin[v]){
  46.                     art_points.insert(v);
  47.                 }
  48.             }
  49.             if (visited[neighbour] == 1 && from[v] != neighbour){
  50.                 up[v] = min(up[v], tin[neighbour]);
  51.             }
  52.         }
  53.         visited[v] = 2;
  54.     }
  55.  
  56.     vector<size_t> children;
  57.     vector<size_t> from;
  58.     set<size_t> art_points;
  59.     size_t time;
  60.     vector<size_t> tin;
  61.     vector<size_t> up;
  62.     vector<int> visited;
  63.     vector<vector<size_t>> graph;
  64. };
  65.  
  66.  
  67. int main(){
  68.     size_t v_amount, e_amount;
  69.     cin >> v_amount >> e_amount;
  70.     Graph graph(v_amount);
  71.     for (int i = 0; i < e_amount; ++i){
  72.         size_t a, b;
  73.         cin >> a >> b;
  74.         graph.add_e(a, b);
  75.     }
  76.     auto ap = graph.get_articulation_points();
  77.     cout << ap.size() << endl;
  78.     for (auto v : ap){
  79.         cout << v << endl;
  80.     }
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement