Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int timer, n;
- vector<bool> visited;
- vector<int> tim, low;
- vector<vector<int>> edges;
- vector<pair<int, int>> bridges;
- int dfs(int v, int p = -1)
- {
- visited[v] = true;
- tim[v] = low[v] = timer++;
- for(int to : edges[v])
- {
- if(to == p) continue;
- if(visited[to])
- low[v] = min(low[v], tim[to]);
- else
- {
- dfs(to, v);
- low[v] = min(low[v], tim[to]);
- if(low[to] > tim[v])
- bridges.push_back({v, to});
- }
- }
- }
- void find_bridges()
- {
- timer = 0, n = edges.size();
- tim.assign(n, -1), low.assign(n, -1), visited.assign(n, false);
- for(int v = 0; v < n; v++)
- if(!visited[v])
- dfs(v);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement