Function
dfs
(at, parent, bridges, id)
Source from the content-addressed store, hash-verified
| 6 | visited = [False] * n |
| 7 | |
| 8 | def dfs(at, parent, bridges, id): |
| 9 | visited[at] = True |
| 10 | low[at] = id |
| 11 | id += 1 |
| 12 | for to in l[at]: |
| 13 | if to == parent: |
| 14 | pass |
| 15 | elif not visited[to]: |
| 16 | dfs(to, at, bridges, id) |
| 17 | low[at] = min(low[at], low[to]) |
| 18 | if at < low[to]: |
| 19 | bridges.append([at, to]) |
| 20 | else: |
| 21 | # This edge is a back edge and cannot be a bridge |
| 22 | low[at] = min(low[at], to) |
| 23 | |
| 24 | bridges = [] |
| 25 | for i in range(n): |
Tested by
no test coverage detected