Builds on Cycle Detection, which you haven’t finished yet.
Tarjan's Bridges & Articulation Points
Return every critical link of a network of n servers, numbered 0 to n - 1, in any order. The links are the pairs in connections: [ai, bi] is a two-way link between servers ai and bi, and together the links let every server reach every other one, directly or through other servers.
A link is critical when taking it away leaves some server unable to reach some other server. A critical link may be returned as [ai, bi] or as [bi, ai].
[[3,1]] is accepted too.Tarjan's Bridges
DFS tree ➔ discovery time and low-link per node ➔ bridge when low[child] > disc[parent]| 1 | from typing import List |
| 2 | |
| 3 | def find_bridges(n: int, edges: List[List[int]]) -> List[List[int]]: |
| 4 | """Tarjan's Bridges (the core of Critical Connections in a Network): every edge |
| 5 | whose removal disconnects the graph. |
| 6 | Time: O(V + E) | Space: O(V + E) |
| 7 | """ |
| 8 | graph = [[] for _ in range(n)] |
| 9 | for i, (u, v) in enumerate(edges): |
| 10 | graph[u].append((v, i)) |
| 11 | graph[v].append((u, i)) |
| 12 | # discovery time; -1 = not reached yet |
| 13 | disc = [-1] * n |
| 14 | # earliest disc the subtree reaches with one back edge |
| 15 | low = [0] * n |
| 16 | bridges = [] |
| 17 | time = 0 |
| 18 | for root in range(n): |
| 19 | if disc[root] != -1: |
| 20 | continue |
| 21 | disc[root] = low[root] = time |
| 22 | time += 1 |
| 23 | # (node, edge id we came in by, next neighbour index) |
| 24 | stack = [(root, -1, 0)] |
| 25 | while stack: |
| 26 | node, in_edge, idx = stack[-1] |
| 27 | if idx < len(graph[node]): |
| 28 | stack[-1] = (node, in_edge, idx + 1) |
| 29 | nxt, edge = graph[node][idx] |
| 30 | if edge == in_edge: |
| 31 | continue # not the tree edge back to the parent |
| 32 | if disc[nxt] == -1: |
| 33 | disc[nxt] = low[nxt] = time # tree edge: go deeper |
| 34 | time += 1 |
| 35 | stack.append((nxt, edge, 0)) |
| 36 | else: |
| 37 | # back edge: reaches an earlier node |
| 38 | low[node] = min(low[node], disc[nxt]) |
| 39 | else: |
| 40 | stack.pop() # node is finished |
| 41 | if stack: |
| 42 | parent = stack[-1][0] |
| 43 | low[parent] = min(low[parent], low[node]) |
| 44 | # nothing below node climbs to parent or above |
| 45 | if low[node] > disc[parent]: |
| 46 | bridges.append([parent, node]) |
| 47 | return bridges |
disc[u] is the order in which the DFS first reached u, and once u is finished, low[u] is the smallest disc its subtree reaches using tree edges down and one other edge up.Number the nodes in DFS order with disc, and let low[node] be the earliest disc that node's subtree can reach through one edge other than the tree edge it came in by; when node finishes, the tree edge parent -> node is a bridge exactly when low[node] > disc[parent]. This is correct because any other route between the two sides of that edge has to leave node's subtree by some edge, and an undirected DFS has no edges across subtrees, so that edge climbs to parent or above and would make low[node] <= disc[parent]. The trap is the comparison: bridges need the strict low[node] > disc[parent]. With >=, which is the test for articulation points, an edge whose subtree climbs back exactly to parent (so it sits on a cycle) is wrongly reported.
See it run
Finding bridges with disc and low, step by step
bridges []
Each circle is a node. The two rows under the graph give disc and low for every node, and the small number under each box is the node.
nowthe node the search is working onstacka node, or a search edge, on the current search pathdonea finished node, or an edge that is not a bridgebackan edge to a node that was reached earlierbridgean edge that disconnects the graph when removed
Start the search at node 0. disc[0] = low[0] = 0, and node 0 goes on stack. Every other disc is -1, which means not reached yet.
Gotcha 1 of 4
- The trap
Gotcha 1: Testing
low[node] >= disc[parent]instead of>Mistakeif low[node] >= disc[parent]:Fixif low[node] > disc[parent]:What happens:
low[node] == disc[parent]means the subtree ofnodeclimbs back exactly toparent. So the edgeparent -> nodelies on a cycle, and removing it disconnects nothing.>=reports it anyway.>=is the test for articulation points, not for bridges.Example: Critical Connections in a Network (LC 1192): n = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]]Mistake: returns [[1, 3], [0, 1]]Fix: returns [[1, 3]]
- You need the edge that closes a cycle as edges arrive one by one, as in Redundant Connection (LC 684), not the edges that no cycle protects. See Union-Find
- You only need to count the connected pieces as they are, as in Number of Provinces (LC 547), not which single removal would split one. See Flood Fill
Deep Dive
Why low[node] > disc[parent] marks a bridge
A bridge is an edge whose removal splits the graph into more pieces. Run a DFS (depth-first search) and give each node a number, disc, in the order the search first reaches it. The edges the search follows to new nodes are tree edges. Every other edge of an undirected graph joins a node to one of its ancestors or descendants, and it is called a back edge.
low[node] is the smallest disc that the subtree of node can reach with tree edges down and one back edge up. When node finishes, look at the tree edge parent -> node. If low[node] > disc[parent], nothing in the subtree of node has any edge to parent or above. The only link between the subtree and the rest of the graph is the edge parent -> node, so it is a bridge.
If low[node] <= disc[parent], some edge from the subtree climbs to parent or above. That edge is a second route, so removing parent -> node disconnects nothing.
An undirected DFS has no edge between two different subtrees. So a second route from the subtree of node can only go up. This is why low needs only the disc of nodes that were already reached.
Example: in the loop 0, 1, 2 with the extra node 3 on node 1, the edge [1, 3] is a bridge and the edges of the loop are not. This is the example of Critical Connections in a Network (LC 1192).
One trace: eight servers, three bridges
The board uses 8 nodes. Nodes 0 to 3 and their edges [0, 1], [1, 2], [2, 0], [1, 3] are the example of Critical Connections in a Network (LC 1192). The extra edges [3, 4], [4, 5], [5, 3], [5, 6], [6, 7] add a second loop and a chain.
The search goes 0, 1, 2. At node 2, the edge to node 0 is a back edge, so low[2] becomes 0. Node 2 finishes, and low[1] becomes 0. Since low[2] = 0 is not greater than disc[1] = 1, the edge 1-2 is not a bridge.
Then the search goes 1, 3, 4, 5, 6, 7. At node 5, the edge to node 3 is a back edge, so low[5] becomes 3. Node 7 finishes first of these nodes. Its low[7] = 7 is greater than disc[6] = 6, so 6-7 is a bridge. Node 6 finishes with low[6] = 6, which is greater than disc[5] = 5, so 5-6 is a bridge.
Node 5 finishes with low[5] = 3, which is not greater than disc[4] = 4. Node 4 finishes with low[4] = 3, and disc[3] = 3. This is not greater, so 3-4 is not a bridge. Node 3 finishes with low[3] = 3, which is greater than disc[1] = 1, so 1-3 is a bridge.
The final answer is [[6, 7], [5, 6], [1, 3]], in the order the bridges were found. The final low values are [0, 0, 0, 3, 3, 3, 6, 7].
The traps: >=, the parent edge, and passing low up
Bridges need the strict test low[node] > disc[parent]. With >=, an edge whose subtree climbs back exactly to parent is reported. That edge is on a cycle. On the board graph, >= reports 5 edges: the 3 real bridges and also 3-4 and 0-1.
The edge back to the parent must be skipped by its id, edge == in_edge. Without the skip, node sees parent through the tree edge, so low[node] <= disc[parent] always holds and no bridge is ever found. The id and not the node is compared, so a second edge between the same two nodes is still treated as a back edge.
low[parent] = min(low[parent], low[node]) must run when node finishes. Without it, low[parent] sees only the back edges of parent itself. On the board graph, leaving that line out reports the same 5 edges as >=: 3-4 and 0-1 look like bridges, because low[4] and low[1] never learn about the back edges in their subtrees.
The search is iterative, with stack holding (node, in_edge, idx). Critical Connections in a Network (LC 1192) allows 10^5 servers in one chain. A recursive dfs would nest 10^5 calls and pass Python's recursion limit.
The cost, and the neighbours
Each node is pushed on stack once. Each entry in graph[node] is read once, so each edge is read twice. The time is O(V + E). graph, disc, low and stack hold at most one entry per node or per edge, so the space is O(V + E).
On the board graph, 8 nodes and 9 edges give 18 neighbour entries. The search reads each entry once.
The same two arrays also find articulation points, which are nodes whose removal splits the graph. That test is low[child] >= disc[node], and the root needs a separate rule. This card finds edges, so the strict test applies.
If edges arrive one at a time and you need the first edge that closes a cycle, use union-find, as in Redundant Connection (LC 684). If you only count the pieces, a plain search is enough, as in Number of Provinces (LC 547). Bridges answer a different question: which single edge is the only link.
60-Second Pitch
"I need the edges whose removal splits the network. I run one DFS and give each node a number, disc, in the order it is reached. For each node I also keep low, the smallest disc its subtree can reach with one back edge. When a node finishes, I pass its low up to its parent. The tree edge from the parent is a bridge exactly when low[node] > disc[parent]. That means nothing below the node has an edge to the parent or above, so this edge is the only link. I skip the edge I came in by, using its id. I use > and not >=, because >= is the articulation point test and reports edges on cycles. Each node and each edge is handled once, so the time is O(V + E) and the space is O(V + E). I use an explicit stack so a long chain cannot pass the recursion limit."
Common Questions
- Why is
low[node] > disc[parent]the right test? low[node]is the smallestdiscthe subtree ofnodecan reach. If it is greater thandisc[parent], no edge from the subtree reachesparentor any node above. So the tree edgeparent -> nodeis the only link between the subtree and the rest of the graph.- Why can a subtree escape only through an edge to an ancestor?
In an undirected DFS, every non-tree edge joins a node to one of its ancestors or descendants. If an edge joined two different subtrees, the search would have followed it and made it a tree edge. So any second route from the subtree of
nodemust go up toparentor above.- What is the difference between a bridge and an articulation point?
A bridge is an edge whose removal increases the number of pieces. An articulation point is a node whose removal does. For a bridge, the test is
low[child] > disc[node]. For an articulation point, it islow[child] >= disc[node], and the root needs its own rule: it is one when it has two or more children in the DFS tree.- What are the time and space complexity?
O(V + E)time andO(V + E)space. Each node entersstackonce, and each edge is read twice, once from each end.graphholds both directions of every edge.- Why use an iterative search?
The input can be one long chain of 10^5 nodes. A recursive
dfswould make one nested call per node, and Python's default limit is 1000 calls. The blueprint keeps(node, in_edge, idx)onstack, so the depth is limited by memory only.
SWE Reasoning
Spot it
- The question asks for the links, roads or cables whose failure splits the network.
- The wording says critical, single point of failure, or the only path between two parts.
- The graph is undirected, and removing one edge or one node can increase the number of pieces.
- The input can be large, up to 10^5 nodes, so the search must be
O(V + E)and iterative. - Checking each edge by removing it and counting pieces would cost O(E * (V + E)). That is too slow.
The invariant, step by step
disc[u]is -1 until the search reachesu. The first time, it gets the next number fromtime, andlow[u]starts equal to it.- The search reads one neighbour at a time from the top of
stack. It skips the edge it came in by,edge == in_edge. - A neighbour with
disc[nxt] == -1is a tree edge. The search sets its numbers and pushes it. - A neighbour that already has a number is a back edge. It lowers
low[node]tomin(low[node], disc[nxt]). - When a node has no neighbour left, it is popped. Its
lowgoes up to the parent withlow[parent] = min(low[parent], low[node]). - The tree edge
parent -> nodeis added tobridgesexactly whenlow[node] > disc[parent]. No edge from the subtree reachesparentor above, so this edge is the only link.
Traps
>=instead of>.low[node] == disc[parent]means the subtree climbs back toparent, so the edge is on a cycle.>=is the test for articulation points, not for bridges.- Following the edge back to the parent. The tree edge is in
graph[node]too. Skip it by its id,edge == in_edge. - Not passing
low[node]to the parent. Thenlow[parent]knows only its own back edges, and edges above a cycle look like bridges. - Recursive
dfs. A chain of 10^5 servers nests 10^5 calls. Python stops at 1000 by default. Keep the path instack. - Skipping the parent by node and not by edge id. Two parallel edges between the same two nodes are not bridges. Compare edge ids so the second edge counts as a back edge.
Practice
Builds on Cycle Detection, which you haven’t finished yet.
Tarjan's Bridges & Articulation Points
Return every critical link of a network of n servers, numbered 0 to n - 1, in any order. The links are the pairs in connections: [ai, bi] is a two-way link between servers ai and bi, and together the links let every server reach every other one, directly or through other servers.
A link is critical when taking it away leaves some server unable to reach some other server. A critical link may be returned as [ai, bi] or as [bi, ai].
[[3,1]] is accepted too.Tarjan's Bridges
DFS tree ➔ discovery time and low-link per node ➔ bridge when low[child] > disc[parent]| 1 | from typing import List |
| 2 | |
| 3 | def find_bridges(n: int, edges: List[List[int]]) -> List[List[int]]: |
| 4 | """Tarjan's Bridges (the core of Critical Connections in a Network): every edge |
| 5 | whose removal disconnects the graph. |
| 6 | Time: O(V + E) | Space: O(V + E) |
| 7 | """ |
| 8 | graph = [[] for _ in range(n)] |
| 9 | for i, (u, v) in enumerate(edges): |
| 10 | graph[u].append((v, i)) |
| 11 | graph[v].append((u, i)) |
| 12 | # discovery time; -1 = not reached yet |
| 13 | disc = [-1] * n |
| 14 | # earliest disc the subtree reaches with one back edge |
| 15 | low = [0] * n |
| 16 | bridges = [] |
| 17 | time = 0 |
| 18 | for root in range(n): |
| 19 | if disc[root] != -1: |
| 20 | continue |
| 21 | disc[root] = low[root] = time |
| 22 | time += 1 |
| 23 | # (node, edge id we came in by, next neighbour index) |
| 24 | stack = [(root, -1, 0)] |
| 25 | while stack: |
| 26 | node, in_edge, idx = stack[-1] |
| 27 | if idx < len(graph[node]): |
| 28 | stack[-1] = (node, in_edge, idx + 1) |
| 29 | nxt, edge = graph[node][idx] |
| 30 | if edge == in_edge: |
| 31 | continue # not the tree edge back to the parent |
| 32 | if disc[nxt] == -1: |
| 33 | disc[nxt] = low[nxt] = time # tree edge: go deeper |
| 34 | time += 1 |
| 35 | stack.append((nxt, edge, 0)) |
| 36 | else: |
| 37 | # back edge: reaches an earlier node |
| 38 | low[node] = min(low[node], disc[nxt]) |
| 39 | else: |
| 40 | stack.pop() # node is finished |
| 41 | if stack: |
| 42 | parent = stack[-1][0] |
| 43 | low[parent] = min(low[parent], low[node]) |
| 44 | # nothing below node climbs to parent or above |
| 45 | if low[node] > disc[parent]: |
| 46 | bridges.append([parent, node]) |
| 47 | return bridges |
disc[u] is the order in which the DFS first reached u, and once u is finished, low[u] is the smallest disc its subtree reaches using tree edges down and one other edge up.Number the nodes in DFS order with disc, and let low[node] be the earliest disc that node's subtree can reach through one edge other than the tree edge it came in by; when node finishes, the tree edge parent -> node is a bridge exactly when low[node] > disc[parent]. This is correct because any other route between the two sides of that edge has to leave node's subtree by some edge, and an undirected DFS has no edges across subtrees, so that edge climbs to parent or above and would make low[node] <= disc[parent]. The trap is the comparison: bridges need the strict low[node] > disc[parent]. With >=, which is the test for articulation points, an edge whose subtree climbs back exactly to parent (so it sits on a cycle) is wrongly reported.
See it run
Finding bridges with disc and low, step by step
bridges []
Each circle is a node. The two rows under the graph give disc and low for every node, and the small number under each box is the node.
nowthe node the search is working onstacka node, or a search edge, on the current search pathdonea finished node, or an edge that is not a bridgebackan edge to a node that was reached earlierbridgean edge that disconnects the graph when removed
Start the search at node 0. disc[0] = low[0] = 0, and node 0 goes on stack. Every other disc is -1, which means not reached yet.
Gotcha 1 of 4
- The trap
Gotcha 1: Testing
low[node] >= disc[parent]instead of>Mistakeif low[node] >= disc[parent]:Fixif low[node] > disc[parent]:What happens:
low[node] == disc[parent]means the subtree ofnodeclimbs back exactly toparent. So the edgeparent -> nodelies on a cycle, and removing it disconnects nothing.>=reports it anyway.>=is the test for articulation points, not for bridges.Example: Critical Connections in a Network (LC 1192): n = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]]Mistake: returns [[1, 3], [0, 1]]Fix: returns [[1, 3]]
- You need the edge that closes a cycle as edges arrive one by one, as in Redundant Connection (LC 684), not the edges that no cycle protects. See Union-Find
- You only need to count the connected pieces as they are, as in Number of Provinces (LC 547), not which single removal would split one. See Flood Fill
Deep Dive
Why low[node] > disc[parent] marks a bridge
A bridge is an edge whose removal splits the graph into more pieces. Run a DFS (depth-first search) and give each node a number, disc, in the order the search first reaches it. The edges the search follows to new nodes are tree edges. Every other edge of an undirected graph joins a node to one of its ancestors or descendants, and it is called a back edge.
low[node] is the smallest disc that the subtree of node can reach with tree edges down and one back edge up. When node finishes, look at the tree edge parent -> node. If low[node] > disc[parent], nothing in the subtree of node has any edge to parent or above. The only link between the subtree and the rest of the graph is the edge parent -> node, so it is a bridge.
If low[node] <= disc[parent], some edge from the subtree climbs to parent or above. That edge is a second route, so removing parent -> node disconnects nothing.
An undirected DFS has no edge between two different subtrees. So a second route from the subtree of node can only go up. This is why low needs only the disc of nodes that were already reached.
Example: in the loop 0, 1, 2 with the extra node 3 on node 1, the edge [1, 3] is a bridge and the edges of the loop are not. This is the example of Critical Connections in a Network (LC 1192).
One trace: eight servers, three bridges
The board uses 8 nodes. Nodes 0 to 3 and their edges [0, 1], [1, 2], [2, 0], [1, 3] are the example of Critical Connections in a Network (LC 1192). The extra edges [3, 4], [4, 5], [5, 3], [5, 6], [6, 7] add a second loop and a chain.
The search goes 0, 1, 2. At node 2, the edge to node 0 is a back edge, so low[2] becomes 0. Node 2 finishes, and low[1] becomes 0. Since low[2] = 0 is not greater than disc[1] = 1, the edge 1-2 is not a bridge.
Then the search goes 1, 3, 4, 5, 6, 7. At node 5, the edge to node 3 is a back edge, so low[5] becomes 3. Node 7 finishes first of these nodes. Its low[7] = 7 is greater than disc[6] = 6, so 6-7 is a bridge. Node 6 finishes with low[6] = 6, which is greater than disc[5] = 5, so 5-6 is a bridge.
Node 5 finishes with low[5] = 3, which is not greater than disc[4] = 4. Node 4 finishes with low[4] = 3, and disc[3] = 3. This is not greater, so 3-4 is not a bridge. Node 3 finishes with low[3] = 3, which is greater than disc[1] = 1, so 1-3 is a bridge.
The final answer is [[6, 7], [5, 6], [1, 3]], in the order the bridges were found. The final low values are [0, 0, 0, 3, 3, 3, 6, 7].
The traps: >=, the parent edge, and passing low up
Bridges need the strict test low[node] > disc[parent]. With >=, an edge whose subtree climbs back exactly to parent is reported. That edge is on a cycle. On the board graph, >= reports 5 edges: the 3 real bridges and also 3-4 and 0-1.
The edge back to the parent must be skipped by its id, edge == in_edge. Without the skip, node sees parent through the tree edge, so low[node] <= disc[parent] always holds and no bridge is ever found. The id and not the node is compared, so a second edge between the same two nodes is still treated as a back edge.
low[parent] = min(low[parent], low[node]) must run when node finishes. Without it, low[parent] sees only the back edges of parent itself. On the board graph, leaving that line out reports the same 5 edges as >=: 3-4 and 0-1 look like bridges, because low[4] and low[1] never learn about the back edges in their subtrees.
The search is iterative, with stack holding (node, in_edge, idx). Critical Connections in a Network (LC 1192) allows 10^5 servers in one chain. A recursive dfs would nest 10^5 calls and pass Python's recursion limit.
The cost, and the neighbours
Each node is pushed on stack once. Each entry in graph[node] is read once, so each edge is read twice. The time is O(V + E). graph, disc, low and stack hold at most one entry per node or per edge, so the space is O(V + E).
On the board graph, 8 nodes and 9 edges give 18 neighbour entries. The search reads each entry once.
The same two arrays also find articulation points, which are nodes whose removal splits the graph. That test is low[child] >= disc[node], and the root needs a separate rule. This card finds edges, so the strict test applies.
If edges arrive one at a time and you need the first edge that closes a cycle, use union-find, as in Redundant Connection (LC 684). If you only count the pieces, a plain search is enough, as in Number of Provinces (LC 547). Bridges answer a different question: which single edge is the only link.
60-Second Pitch
"I need the edges whose removal splits the network. I run one DFS and give each node a number, disc, in the order it is reached. For each node I also keep low, the smallest disc its subtree can reach with one back edge. When a node finishes, I pass its low up to its parent. The tree edge from the parent is a bridge exactly when low[node] > disc[parent]. That means nothing below the node has an edge to the parent or above, so this edge is the only link. I skip the edge I came in by, using its id. I use > and not >=, because >= is the articulation point test and reports edges on cycles. Each node and each edge is handled once, so the time is O(V + E) and the space is O(V + E). I use an explicit stack so a long chain cannot pass the recursion limit."
Common Questions
- Why is
low[node] > disc[parent]the right test? low[node]is the smallestdiscthe subtree ofnodecan reach. If it is greater thandisc[parent], no edge from the subtree reachesparentor any node above. So the tree edgeparent -> nodeis the only link between the subtree and the rest of the graph.- Why can a subtree escape only through an edge to an ancestor?
In an undirected DFS, every non-tree edge joins a node to one of its ancestors or descendants. If an edge joined two different subtrees, the search would have followed it and made it a tree edge. So any second route from the subtree of
nodemust go up toparentor above.- What is the difference between a bridge and an articulation point?
A bridge is an edge whose removal increases the number of pieces. An articulation point is a node whose removal does. For a bridge, the test is
low[child] > disc[node]. For an articulation point, it islow[child] >= disc[node], and the root needs its own rule: it is one when it has two or more children in the DFS tree.- What are the time and space complexity?
O(V + E)time andO(V + E)space. Each node entersstackonce, and each edge is read twice, once from each end.graphholds both directions of every edge.- Why use an iterative search?
The input can be one long chain of 10^5 nodes. A recursive
dfswould make one nested call per node, and Python's default limit is 1000 calls. The blueprint keeps(node, in_edge, idx)onstack, so the depth is limited by memory only.
SWE Reasoning
Spot it
- The question asks for the links, roads or cables whose failure splits the network.
- The wording says critical, single point of failure, or the only path between two parts.
- The graph is undirected, and removing one edge or one node can increase the number of pieces.
- The input can be large, up to 10^5 nodes, so the search must be
O(V + E)and iterative. - Checking each edge by removing it and counting pieces would cost O(E * (V + E)). That is too slow.
The invariant, step by step
disc[u]is -1 until the search reachesu. The first time, it gets the next number fromtime, andlow[u]starts equal to it.- The search reads one neighbour at a time from the top of
stack. It skips the edge it came in by,edge == in_edge. - A neighbour with
disc[nxt] == -1is a tree edge. The search sets its numbers and pushes it. - A neighbour that already has a number is a back edge. It lowers
low[node]tomin(low[node], disc[nxt]). - When a node has no neighbour left, it is popped. Its
lowgoes up to the parent withlow[parent] = min(low[parent], low[node]). - The tree edge
parent -> nodeis added tobridgesexactly whenlow[node] > disc[parent]. No edge from the subtree reachesparentor above, so this edge is the only link.
Traps
>=instead of>.low[node] == disc[parent]means the subtree climbs back toparent, so the edge is on a cycle.>=is the test for articulation points, not for bridges.- Following the edge back to the parent. The tree edge is in
graph[node]too. Skip it by its id,edge == in_edge. - Not passing
low[node]to the parent. Thenlow[parent]knows only its own back edges, and edges above a cycle look like bridges. - Recursive
dfs. A chain of 10^5 servers nests 10^5 calls. Python stops at 1000 by default. Keep the path instack. - Skipping the parent by node and not by edge id. Two parallel edges between the same two nodes are not bridges. Compare edge ids so the second edge counts as a back edge.