Advertisement
Josif_tepe

Untitled

Dec 12th, 2022
604
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 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 discoverable_time[maxn];
  10. int low_link[maxn];
  11. bool visited[maxn];
  12. int current_time = 0;
  13. void dfs(int node, int parent = -1) {
  14.     visited[node] = true;
  15.     low_link[node] = current_time;
  16.     discoverable_time[node] = current_time;
  17.     current_time++;
  18.    
  19.     for(int i = 0; i < (int) graph[node].size(); i++) {
  20.         int neighbour = graph[node][i];
  21.         if(neighbour != parent) {
  22.             if(visited[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. void bridges() {
  36.     for(int i = 0; i < maxn; i++) {
  37.         visited[i] = false;
  38.         discoverable_time[i] = -1;
  39.         low_link[i] = -1;
  40.     }
  41.     for(int i = 0; i < n; i++) {
  42.         if(!visited[i]) {
  43.             dfs(i);
  44.         }
  45.     }
  46. }
  47.  
  48. int main()
  49. {
  50.     cin >> n >> m;
  51.     for(int i = 0; i < m; i++) {
  52.         int a, b;
  53.         cin >> a >> b;
  54.         a--; b--;
  55.         graph[a].push_back(b);
  56.         graph[b].push_back(a);
  57.     }
  58.     bridges();
  59.     return 0;
  60. }
  61.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement