Advertisement
keverman

Bridges

Feb 5th, 2020
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.73 KB | None | 0 0
  1. int timer, n;
  2. vector<bool> visited;
  3. vector<int> tim, low;
  4. vector<vector<int>> edges;
  5. vector<pair<int, int>> bridges;
  6.  
  7. int dfs(int v, int p = -1)
  8. {
  9.     visited[v] = true;
  10.     tim[v] = low[v] = timer++;
  11.     for(int to : edges[v])
  12.     {
  13.         if(to == p) continue;
  14.         if(visited[to])
  15.             low[v] = min(low[v], tim[to]);
  16.         else
  17.         {
  18.             dfs(to, v);
  19.             low[v] = min(low[v], tim[to]);
  20.             if(low[to] > tim[v])
  21.                 bridges.push_back({v, to});
  22.         }
  23.     }
  24. }
  25.  
  26. void find_bridges()
  27. {
  28.     timer = 0, n = edges.size();
  29.     tim.assign(n, -1), low.assign(n, -1), visited.assign(n, false);
  30.  
  31.     for(int v = 0; v < n; v++)
  32.         if(!visited[v])
  33.             dfs(v);
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement