Advertisement
Josif_tepe

Untitled

Dec 11th, 2022
885
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 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.     for(int i = 0; i < (int) graph[node].size(); i++) {
  20.         int neighbour = graph[node][i];
  21.         if(neighbour != parent) {
  22.             if(on_stack[neighbour]) {
  23.                 low_link[node] = min(low_link[node], discoverable_time[neighbour]);
  24.             }
  25.             else {
  26.                 dfs(neighbour, node);
  27.                 if(discoverable_time[node] < low_link[neighbour]) {
  28.                     cout << "Bridge between: " << node + 1 << " " << neighbour + 1 << endl;
  29.                 }
  30.                 low_link[node] = min(low_link[node], low_link[neighbour]);
  31.              
  32.             }
  33.         }
  34.     }
  35.  
  36. }
  37. void bridges() {
  38.     for(int i = 0; i < maxn; i++) {
  39.         discoverable_time[i] = -1;
  40.         on_stack[i] = false;
  41.         low_link[i] = -1;
  42.     }
  43.     for(int i = 0; i < n; i++) {
  44.         if(!on_stack[i]) {
  45.             dfs(i);
  46.         }
  47.     }
  48. }
  49. int main()
  50. {
  51.     cin >> n >> m;
  52.     for(int i = 0; i < m; i++) {
  53.         int a, b;
  54.         cin >>  a >> b;
  55.         a--;b--;
  56.         graph[a].push_back(b);
  57.         graph[b].push_back(a);
  58.     }
  59.     bridges();
  60.     return 0;
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement