Advertisement
Josif_tepe

Untitled

Dec 11th, 2022
871
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <stack>
  5. using namespace std;
  6. const int maxn = 1e5 + 10;
  7. int n, m;
  8. vector<int> graph[maxn];
  9. int low_link[maxn];
  10. int discoverable_time[maxn];
  11. bool on_stack[maxn];
  12. int timer = 0;
  13. void dfs(int node, int parent = -1) {
  14.     on_stack[node] = true;
  15.     low_link[node] = timer;
  16.     discoverable_time[node] = timer;
  17.     timer++;
  18.    
  19.     int children_of_root = 0;
  20.     for(int i = 0; i < (int) graph[node].size(); i++) {
  21.         int neighbour = graph[node][i];
  22.         if(neighbour != parent) {
  23.             if(on_stack[neighbour]) {
  24.                 low_link[node] = min(low_link[node], discoverable_time[neighbour]);
  25.             }
  26.             else {
  27.                 dfs(neighbour, node);
  28.                 low_link[node] = min(low_link[node], low_link[neighbour]);
  29.                 if(parent != -1 and low_link[neighbour] >= discoverable_time[node]) {
  30.                     cout << "Articulation point: " << node + 1 << endl;
  31.                 }
  32.                 children_of_root++;
  33.             }
  34.         }
  35.     }
  36.     if(children_of_root > 1 and parent == -1) {
  37.         cout << "Articulation point: " << node + 1 << endl;
  38.     }
  39. }
  40. void articulation_points() {
  41.     for(int i = 0; i < maxn; i++) {
  42.         discoverable_time[i] = -1;
  43.         on_stack[i] = false;
  44.         low_link[i] = -1;
  45.     }
  46.     for(int i = 0; i < n; i++) {
  47.         if(!on_stack[i]) {
  48.             dfs(i);
  49.         }
  50.     }
  51. }
  52. int main()
  53. {
  54.     cin >> n >> m;
  55.     for(int i = 0; i < m; i++) {
  56.         int a, b;
  57.         cin >>  a >> b;
  58.         a--;b--;
  59.         graph[a].push_back(b);
  60.         graph[b].push_back(a);
  61.     }
  62.     articulation_points();
  63.     return 0;
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement