Advertisement
Josif_tepe

Untitled

Oct 17th, 2023
1,174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. using namespace std;
  5. const int maxn = 1e5 + 10;
  6. vector<int> graph[maxn];
  7. int discovarable_time[maxn];
  8. int low_link[maxn];
  9. bool on_stack[maxn];
  10. int current_time = 0;
  11. int n;
  12.  
  13. void dfs(int node, int parent) {
  14.     on_stack[node] = true;
  15.     low_link[node] = current_time;
  16.     discovarable_time[node] = current_time;
  17.     current_time++;
  18.    
  19.     int 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], discovarable_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] >= discovarable_time[node]) {
  30.                     cout << "articulation point: " << node + 1 << endl;
  31.                 }
  32.                 root++;
  33.             }
  34.         }
  35.     }
  36.     if(root > 1 and parent == -1) {
  37.         cout << "articulation point: " << node + 1 << endl;
  38.     }
  39. }
  40. void art_points() {
  41.     for(int i = 0; i < maxn; i++) {
  42.         discovarable_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, -1);
  49.            
  50.         }
  51.     }
  52. }
  53. int main() {
  54.     int  m;
  55.     cin >> n >> m;
  56.    
  57.     for(int i = 0; i < m; i++) {
  58.         int a, b;
  59.         cin >> a >> b;
  60.         a--; b--;
  61.         graph[a].push_back(b);
  62.         graph[b].push_back(a);
  63.     }
  64.    
  65.     art_points();
  66.     return 0;
  67. }
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement