Prompt and Applicable Context
You are given n nodes labeled 0 through n - 1 and an array connections, where each pair [u, v] is an undirected edge. The graph is connected and simple: it has no self-loops or repeated edges. Return every critical connection, meaning every edge whose removal disconnects the graph. The answer may be in any order, and either endpoint order is acceptable.
Assume 2 <= n <= 100000 and n - 1 <= connections.length <= 100000. For example:
n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
output = [[1, 3]]The first three edges form a cycle, so removing any one of them leaves an alternate route. Node 3 has only the edge [1, 3]; removing it separates node 3. In graph terminology, a critical connection is a bridge.
This is a coding question about graph invariants. It differs from the existing Union-Find article, which maintains connected components while edges are added; it differs from topological sorting, which orders a directed acyclic graph; and it differs from Dijkstra, which optimizes weighted path length. Here the output depends on how connectivity changes after removing each undirected edge.
What the Interviewer Evaluates
The first signal is whether the candidate rejects the obvious repeated-search approach at the stated scale. Removing one edge and running BFS or DFS answers one query correctly, but repeating that for all m edges costs O(m(n + m)) time. At 100,000 edges, a linear traversal per edge is not viable.
The second signal is a precise low-link invariant. A DFS discovery time tin[u] records when u is first visited. low[u] is the earliest discovery time reachable from u's DFS subtree by descending tree edges and then using at most one non-tree edge. For a DFS tree edge u -> v, the edge is a bridge exactly when low[v] > tin[u].
The third signal is implementation discipline. On an already visited neighbor, update with tin[neighbor], not low[neighbor]. Skip the exact edge used to enter a node, not every edge whose other endpoint equals the parent. Edge IDs make that distinction explicit and keep the code correct if a follow-up permits parallel edges.
The fourth signal is production-language awareness. A recursive DFS is concise, but a chain of 100,000 nodes can exceed a JavaScript runtime's call-stack limit. An iterative DFS must simulate both the entry phase and the return-from-child phase so it can propagate low values only after a child has finished.
Questions to Clarify Before Answering
- Is the graph directed? No. Bridges in a directed graph require a different definition and
algorithm.
- Is the graph guaranteed to be connected? Yes for the base prompt. Iterating over every
unvisited node costs nothing asymptotically and makes the implementation work for a disconnected follow-up too.
- Are repeated edges allowed? No in the base prompt. The implementation still gives every edge
an ID, so two parallel edges would correctly provide alternate routes rather than both being reported as bridges.
- May the result use either endpoint order? Yes. If a judge requires canonical output, normalize
each edge to [min, max] and sort only after finding the bridges.
- Is the graph static? Yes. Maintaining bridges while edges are inserted or deleted is a dynamic
connectivity problem; rerunning this linear algorithm after each update may be too expensive.
- Can I use recursion? Only if the environment guarantees enough stack depth. With
nup to
100,000 in JavaScript or TypeScript, an explicit stack is the safer contract.
30-Second Answer Framework
“I would run DFS once and assign every node a discovery time tin. For each node, low records the earliest discovery time reachable from its DFS subtree without going back through the exact tree edge that entered it. After a child v finishes, if low[v] > tin[u], the subtree under v has no route to u or an ancestor, so [u, v] is a bridge. Otherwise a back edge provides an alternate route. I will use edge IDs and an explicit DFS stack to handle parallel-edge follow-ups and avoid call-stack overflow. Every adjacency entry is processed once, so time is O(n + m) and space is O(n + m).”
Step-by-Step Deep Dive
Start with the correct but slow baseline. For each edge, temporarily ignore it and traverse from one endpoint. If the other endpoint becomes unreachable, that edge is a bridge. One traversal takes O(n + m), so all edges take O(m(n + m)). This method can be reasonable for a tiny graph or a one-off check because it is easy to audit, but it misses the required scale.
DFS exposes all alternate routes in one pass. When a node u is first entered, assign tin[u] = low[u] = timer and increment timer. A newly visited neighbor becomes a DFS child. An already visited neighbor reached through a different edge is a non-tree connection, so it can lower low[u] to tin[neighbor]. Once a child v finishes, its entire subtree is known, and low[u] = min(low[u], low[v]) propagates that reachability upward.
The strict comparison matters. If low[v] < tin[u], the child subtree reaches an ancestor of u. If low[v] == tin[u], it reaches u itself through another route. Both cases mean the tree edge [u, v] lies on a cycle. Only low[v] > tin[u] proves that every route from the child subtree to the already discovered side uses [u, v].
An iterative implementation stores nextIndex[u], the next adjacency entry still to inspect. The node remains on the stack while its children run. When all of its adjacency entries are consumed, it is popped; that event simulates returning from the recursive call and is the correct moment to update its parent.
type AdjacentEdge = readonly [to: number, edgeId: number]
function findCriticalConnections(
n: number,
connections: ReadonlyArray<readonly [number, number]>,
): number[][] {
const graph: AdjacentEdge[][] = Array.from({ length: n }, () => [])
connections.forEach(([from, to], edgeId) => {
graph[from].push([to, edgeId])
graph[to].push([from, edgeId])
})
const tin = new Array<number>(n).fill(-1)
const low = new Array<number>(n).fill(-1)
const parent = new Array<number>(n).fill(-1)
const parentEdge = new Array<number>(n).fill(-1)
const nextIndex = new Array<number>(n).fill(0)
const bridges: number[][] = []
let timer = 0
for (let root = 0; root < n; root += 1) {
if (tin[root] !== -1) continue
tin[root] = timer
low[root] = timer
timer += 1
const stack = [root]
while (stack.length > 0) {
const node = stack[stack.length - 1]
if (nextIndex[node] < graph[node].length) {
const [neighbor, edgeId] = graph[node][nextIndex[node]]
nextIndex[node] += 1
if (edgeId === parentEdge[node]) continue
if (tin[neighbor] === -1) {
parent[neighbor] = node
parentEdge[neighbor] = edgeId
tin[neighbor] = timer
low[neighbor] = timer
timer += 1
stack.push(neighbor)
} else {
low[node] = Math.min(low[node], tin[neighbor])
}
} else {
stack.pop()
const parentNode = parent[node]
if (parentNode !== -1) {
if (low[node] > tin[parentNode]) {
bridges.push([parentNode, node])
}
low[parentNode] = Math.min(low[parentNode], low[node])
}
}
}
}
return bridges
}The outer loop is redundant for the connected base input but correctly starts a DFS in every component if that guarantee is removed. Edge IDs are more robust than skipping by parent node. With two parallel edges between u and v, the child skips only the tree edge; the second edge is seen as an alternate route and lowers its low value.
For correctness, consider a DFS tree edge u -> v after v has finished. By the definition of low[v], a value at most tin[u] witnesses a non-tree route from v's subtree to u or an ancestor. Combined with tree paths, that route forms a cycle containing [u, v], so removal cannot separate the subtree. If low[v] > tin[u], no such route exists. Every path from that subtree to the previously discovered part must cross [u, v], so removing it increases the component count. The condition is therefore both necessary and sufficient.
Each undirected edge appears twice in the adjacency lists, and each entry is inspected once. Each node is pushed and popped once. Time is O(n + m). The graph, arrays, stack, and output use O(n + m) space; excluding the graph and returned answer, auxiliary space is O(n).
Adversarial tests should compare normalized edge sets, because result order is unspecified. A single edge must be a bridge; a cycle must have none; every edge of a tree must be a bridge; and two cycles joined by one edge must report only the connector. Also test a 100,000-node chain to expose recursive stack risk. For extra confidence, generate small random graphs and compare the linear algorithm with the remove-one-edge baseline.
High-Quality Sample Answer
“A direct solution removes each edge and reruns a traversal, but that costs O(m(n + m)). I can reuse one DFS by recording discovery time and the earliest discovery time reachable from each DFS subtree.
When I enter node u, I initialize tin[u] and low[u] to the current timer. A tree child is fully processed before its low value is propagated to u. For an already visited neighbor reached by a different edge, I update with that neighbor's tin, because that edge itself is the one non-tree escape represented by the invariant.
After child v finishes, [u, v] is a bridge exactly when low[v] > tin[u]. Equality is not enough: it means the subtree has another route back to u, so the edge belongs to a cycle. A greater value means no node in the subtree can reach u or an ancestor without using the tree edge, and removing it separates the subtree.
I would implement the DFS iteratively for the 100,000-node bound. The stack keeps a node until every adjacency entry has been processed, which gives me a return event for propagating the child's low value. I also store the parent edge ID and skip exactly that edge. This handles a parallel-edge follow-up correctly. Every adjacency entry is inspected once, so time is O(n + m) and total space is O(n + m). I would test a cycle, a tree, two cycles with one connector, a long chain, disconnected components, and parallel edges, then differential-test small random graphs against the baseline.”
Common Mistakes
- Rerunning DFS for every edge → correctness is fine but the worst case is quadratic or worse →
Use one DFS and preserve alternate-route information in low.
- Checking
low[child] >= tin[parent]→ equality already witnesses another path back to the
parent → Use the strict condition low[child] > tin[parent].
- Updating a visited neighbor with
low[neighbor]→ reachability from another DFS subtree leaks
across a non-tree edge and can hide a real bridge → **Use tin[neighbor] for an already visited neighbor and low[child] only after a tree child finishes.**
- Skipping every edge to the parent node → parallel edges are all ignored and one may be reported
as a bridge → Assign edge IDs and skip only the edge used to enter the node.
- Testing the bridge before the child finishes → the child's alternate routes are not yet known →
Evaluate the condition during the simulated return phase.
- Starting only at node 0 → a disconnected follow-up loses other components → **Start from every
still-unvisited node.**
- Using recursion without checking stack limits → a long chain can fail despite linear
complexity → Use an explicit stack or prove the runtime supports the required depth.
Follow-Up Questions and Responses
Follow-up 1: What changes if the graph is disconnected?
Define a bridge as an edge whose removal increases the total number of connected components. The same low-link condition applies inside each component. Start DFS from every node whose discovery time is still -1; the provided implementation already does this. Do not require the entire graph to become disconnected after removal.
Follow-up 2: What if parallel edges and self-loops are allowed?
Keep a unique ID for every edge and skip only parentEdge[node]. A second edge to the parent then acts as a non-tree route, preventing either parallel edge from being classified as a bridge. A self-loop updates a node with its own discovery time and can never be a bridge. The base prompt excludes both cases, but the implementation's edge identity gives the right extension.
Follow-up 3: How would you return articulation points instead?
The low-link data is reusable, but the condition moves from edges to vertices. A non-root node u is an articulation point when it has a DFS child v with low[v] >= tin[u]. A DFS root is an articulation point only when it has at least two DFS-tree children. Notice that equality belongs in the vertex condition, while bridge detection uses strict >.
Follow-up 4: What changes when edges are added continuously?
This algorithm answers a static snapshot in linear time. Recomputing after each insertion costs O(n + m) per update. An insertion-only workload can maintain bridge information with a specialized online data structure; arbitrary additions and deletions require a more general dynamic-connectivity design. Clarify the update type, query rate, and consistency requirement before selecting one.
Follow-up 5: When is the repeated-search baseline still the better answer?
For a tiny graph, a single suspected edge, or diagnostic code where simplicity dominates latency, skipping one edge and running BFS is shorter and easier to inspect. State its O(n + m) cost for one edge and avoid introducing low-link state unless the task actually asks for all bridges or repeated queries.