{"title":"Tarjan's Algorithm","description":"","content":"# Tarjan's Algorithm\n\nimport Tabs from '@theme/Tabs'; import TabItem from '@theme/TabItem';\n\nMost graph algorithms need multiple passes to do anything useful. Kosaraju's algorithm, for example, runs DFS twice and reverses the entire graph in between. Tarjan's algorithm finds every strongly connected component in a directed graph with a single DFS pass. No graph reversal, no second traversal. Just one clean sweep.\n\nThat elegance is not just academic. Tarjan's algorithm is the foundation for finding bridges, articulation points, and 2-edge-connected components. These concepts show up in network reliability problems, compiler optimization (finding loops in control flow graphs), and, of course, coding interviews.\n\nIn this chapter, we will break down how Tarjan's algorithm works, trace through it step by step, and then extend the core idea to find bridges and articulation points. By the end, you will understand not just the mechanics, but the intuition behind why it works.\n\n---\n\n## What Is Tarjan's Algorithm?\n\nTarjan's algorithm is a depth-first search based algorithm that finds all **strongly connected components (SCCs)** in a directed graph in O(V + E) time using a single pass.\n\nA strongly connected component is a maximal group of vertices where every vertex can reach every other vertex through directed edges. \"Maximal\" means you cannot add any more vertices to the group without breaking this property.\n\nConsider this directed graph:\n\n\n```mermaid\nflowchart LR\n A:::primary --> B:::primary\n B --> C:::primary\n C --> A\n C --> D:::orange\n D --> E:::orange\n E --> D\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nThere are two SCCs here: {A, B, C} and {D, E}. Within {A, B, C}, you can follow directed edges from any vertex to any other. Same for {D, E}. But you cannot get from D or E back to A, B, or C, so these two groups remain separate components.\n\nRobert Tarjan published this algorithm in 1972, and it remains one of the most elegant graph algorithms ever designed. The key insight is that during a single DFS, you can gather enough information to identify all SCCs without needing a second pass.\n\n**Interview Insight:** Interviewers rarely ask you to implement Tarjan's from scratch, but they frequently ask problems that require finding SCCs, bridges, or articulation points. Understanding Tarjan's gives you the tools to solve all three.\n\n---\n\n## Key Concepts\n\nTarjan's algorithm relies on two values tracked for every vertex during the DFS traversal.\n\n### Discovery Time (disc)\n\nThe **discovery time** of a vertex is the order in which DFS first visits it. The first vertex visited gets disc = 0, the second gets disc = 1, and so on. This simply timestamps when each vertex was discovered.\n\n### Low-Link Value (low)\n\nThe **low-link value** of a vertex is the smallest discovery time reachable from that vertex through the DFS subtree, including back edges. In simpler terms, it answers the question: \"What is the earliest visited vertex I can reach if I follow DFS edges and then take at most one back edge?\"\n\nInitially, low[u] = disc[u] for every vertex u. As the DFS explores neighbors, low[u] gets updated if a path back to an earlier vertex is found.\n\n### The Root Condition\n\nA vertex u is the **root** of a strongly connected component if disc[u] == low[u]. This means that u cannot reach any vertex discovered earlier than itself, which means u is the \"entry point\" of its SCC in the DFS tree.\n\nWhen this condition is met, everything on the stack from u to the top forms one complete SCC.\n\n\n```mermaid\nflowchart TD\n subgraph SCC[\"Strongly Connected Component\"]\n direction TB\n U[\"u
disc=2, low=2
(root: disc == low)\"]:::green\n V[\"v
disc=3, low=2\"]:::primary\n W[\"w
disc=4, low=2\"]:::primary\n end\n\n U --> V\n V --> W\n W --> U\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nIn this diagram, vertex u has disc = 2 and low = 2, making it the root of the SCC. Vertices v and w both have low = 2 because they can reach u (discovered at time 2) through the back edge from w to u. All three vertices form one SCC.\n\n**Interview Insight:** The low-link value is the trickiest part of Tarjan's algorithm to explain in an interview. Think of it as \"how far back in time can I reach?\" If a vertex can reach back to something discovered earlier, it is part of a cycle, and therefore part of a larger SCC.\n\n---\n\n## How Tarjan's Works\n\nHere is the algorithm in plain English:\n\n1. **Initialize:** Set a global timer to 0. Create arrays disc[] and low[], initialized to -1 (unvisited). Create an empty stack and a boolean array onStack[].\n\n1. **Start DFS** from any unvisited vertex u:\n\n- Set disc[u] = low[u] = timer++\n- Push u onto the stack and mark onStack[u] = true\n\n1. **For each neighbor v of u:**\n\n- If v is unvisited, recurse on v. After the recursion returns, update low[u] = min(low[u], low[v]).\n- If v is already on the stack (meaning v is part of the current DFS path and not yet assigned to an SCC), update low[u] = min(low[u], disc[v]).\n\n1. **After processing all neighbors of u:** If disc[u] == low[u], then u is the root of an SCC. Pop vertices from the stack until u is popped. All popped vertices form one SCC.\n\n1. **Repeat** for any remaining unvisited vertices (the graph may not be connected).\n\nThe stack is critical here. It holds all vertices in the current DFS path that have not yet been assigned to an SCC. When we find a root (disc == low), we know everything above it on the stack belongs to the same SCC.\n\n\n```mermaid\nflowchart TD\n Start[\"Start DFS at vertex u\"]:::primary\n SetDisc[\"Set disc[u] = low[u] = timer++
Push u onto stack\"]:::primary\n ForEach[\"For each neighbor v of u\"]:::orange\n Unvisited{\"Is v unvisited?\"}:::orange\n Recurse[\"Recurse DFS(v)
low[u] = min(low[u], low[v])\"]:::teal\n OnStack{\"Is v on stack?\"}:::orange\n UpdateLow[\"low[u] = min(low[u], disc[v])\"]:::teal\n CheckRoot{\"disc[u] == low[u]?\"}:::orange\n PopSCC[\"Pop stack until u
All popped = one SCC\"]:::green\n Done[\"Return\"]:::primary\n\n Start --> SetDisc --> ForEach\n ForEach --> Unvisited\n Unvisited -- Yes --> Recurse --> ForEach\n Unvisited -- No --> OnStack\n OnStack -- Yes --> UpdateLow --> ForEach\n OnStack -- No --> ForEach\n ForEach -- All neighbors done --> CheckRoot\n CheckRoot -- Yes --> PopSCC --> Done\n CheckRoot -- No --> Done\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nOne subtle but important detail: when we encounter a neighbor v that is already visited, we only update low[u] if v is **currently on the stack**. If v has already been popped and assigned to a different SCC, we ignore it. This is what prevents SCCs from incorrectly merging.\n\n---\n\n## Implementation\n\nHere is the full implementation of Tarjan's algorithm for finding strongly connected components.\n\n \n\n\n```java\nimport java.util.*;\n\npublic class TarjanSCC {\n private int timer = 0;\n private int[] disc;\n private int[] low;\n private boolean[] onStack;\n private Deque stack;\n private List> sccs;\n private List> adj;\n\n public List> findSCCs(int n, List> adj) {\n this.adj = adj;\n disc = new int[n];\n low = new int[n];\n onStack = new boolean[n];\n stack = new ArrayDeque<>();\n sccs = new ArrayList<>();\n Arrays.fill(disc, -1);\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n dfs(i);\n }\n }\n return sccs;\n }\n\n private void dfs(int u) {\n disc[u] = low[u] = timer++;\n stack.push(u);\n onStack[u] = true;\n\n for (int v : adj.get(u)) {\n if (disc[v] == -1) {\n // v is unvisited, recurse\n dfs(v);\n low[u] = Math.min(low[u], low[v]);\n } else if (onStack[v]) {\n // v is on stack, part of current SCC\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n\n // If u is the root of an SCC\n if (disc[u] == low[u]) {\n List scc = new ArrayList<>();\n while (true) {\n int v = stack.pop();\n onStack[v] = false;\n scc.add(v);\n if (v == u) break;\n }\n sccs.add(scc);\n }\n }\n}\n```\n\n\n \n\n\n```python\nfrom collections import defaultdict\n\nclass TarjanSCC:\n def __init__(self):\n self.timer = 0\n self.disc: list[int] = []\n self.low: list[int] = []\n self.on_stack: list[bool] = []\n self.stack: list[int] = []\n self.sccs: list[list[int]] = []\n self.adj: list[list[int]] = []\n\n def find_sccs(self, n: int, adj: list[list[int]]) -> list[list[int]]:\n self.adj = adj\n self.disc = [-1] * n\n self.low = [-1] * n\n self.on_stack = [False] * n\n self.stack = []\n self.sccs = []\n self.timer = 0\n\n for i in range(n):\n if self.disc[i] == -1:\n self._dfs(i)\n return self.sccs\n\n def _dfs(self, u: int) -> None:\n self.disc[u] = self.low[u] = self.timer\n self.timer += 1\n self.stack.append(u)\n self.on_stack[u] = True\n\n for v in self.adj[u]:\n if self.disc[v] == -1:\n # v is unvisited, recurse\n self._dfs(v)\n self.low[u] = min(self.low[u], self.low[v])\n elif self.on_stack[v]:\n # v is on stack, part of current SCC\n self.low[u] = min(self.low[u], self.disc[v])\n\n # If u is the root of an SCC\n if self.disc[u] == self.low[u]:\n scc: list[int] = []\n while True:\n v = self.stack.pop()\n self.on_stack[v] = False\n scc.append(v)\n if v == u:\n break\n self.sccs.append(scc)\n```\n\n\n \n\n\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\nclass TarjanSCC {\n int timer = 0;\n vector disc, low;\n vector onStack;\n stack st;\n vector> sccs;\n vector>& adj;\n\n void dfs(int u) {\n disc[u] = low[u] = timer++;\n st.push(u);\n onStack[u] = true;\n\n for (int v : adj[u]) {\n if (disc[v] == -1) {\n // v is unvisited, recurse\n dfs(v);\n low[u] = min(low[u], low[v]);\n } else if (onStack[v]) {\n // v is on stack, part of current SCC\n low[u] = min(low[u], disc[v]);\n }\n }\n\n // If u is the root of an SCC\n if (disc[u] == low[u]) {\n vector scc;\n while (true) {\n int v = st.top(); st.pop();\n onStack[v] = false;\n scc.push_back(v);\n if (v == u) break;\n }\n sccs.push_back(scc);\n }\n }\n\npublic:\n vector> findSCCs(int n, vector>& adjacency) {\n adj = adjacency;\n disc.assign(n, -1);\n low.assign(n, -1);\n onStack.assign(n, false);\n sccs.clear();\n timer = 0;\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n dfs(i);\n }\n }\n return sccs;\n }\n\n TarjanSCC(vector>& adjacency) : adj(adjacency) {}\n};\n```\n\n\n \n\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\npublic class TarjanSCC {\n private int timer = 0;\n private int[] disc;\n private int[] low;\n private bool[] onStack;\n private Stack stack;\n private List> sccs;\n private List> adj;\n\n public List> FindSCCs(int n, List> adj) {\n this.adj = adj;\n disc = new int[n];\n low = new int[n];\n onStack = new bool[n];\n stack = new Stack();\n sccs = new List>();\n Array.Fill(disc, -1);\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n Dfs(i);\n }\n }\n return sccs;\n }\n\n private void Dfs(int u) {\n disc[u] = low[u] = timer++;\n stack.Push(u);\n onStack[u] = true;\n\n foreach (int v in adj[u]) {\n if (disc[v] == -1) {\n // v is unvisited, recurse\n Dfs(v);\n low[u] = Math.Min(low[u], low[v]);\n } else if (onStack[v]) {\n // v is on stack, part of current SCC\n low[u] = Math.Min(low[u], disc[v]);\n }\n }\n\n // If u is the root of an SCC\n if (disc[u] == low[u]) {\n var scc = new List();\n while (true) {\n int v = stack.Pop();\n onStack[v] = false;\n scc.Add(v);\n if (v == u) break;\n }\n sccs.Add(scc);\n }\n }\n}\n```\n\n\n \n\n\n```go\npackage tarjan\n\nfunc FindSCCs(n int, adj [][]int) [][]int {\n\ttimer := 0\n\tdisc := make([]int, n)\n\tlow := make([]int, n)\n\tonStack := make([]bool, n)\n\tstack := []int{}\n\tsccs := [][]int{}\n\n\tfor i := range disc {\n\t\tdisc[i] = -1\n\t}\n\n\tvar dfs func(u int)\n\tdfs = func(u int) {\n\t\tdisc[u] = timer\n\t\tlow[u] = timer\n\t\ttimer++\n\t\tstack = append(stack, u)\n\t\tonStack[u] = true\n\n\t\tfor _, v := range adj[u] {\n\t\t\tif disc[v] == -1 {\n\t\t\t\t// v is unvisited, recurse\n\t\t\t\tdfs(v)\n\t\t\t\tif low[v] < low[u] {\n\t\t\t\t\tlow[u] = low[v]\n\t\t\t\t}\n\t\t\t} else if onStack[v] {\n\t\t\t\t// v is on stack, part of current SCC\n\t\t\t\tif disc[v] < low[u] {\n\t\t\t\t\tlow[u] = disc[v]\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\t// If u is the root of an SCC\n\t\tif disc[u] == low[u] {\n\t\t\tscc := []int{}\n\t\t\tfor {\n\t\t\t\tv := stack[len(stack)-1]\n\t\t\t\tstack = stack[:len(stack)-1]\n\t\t\t\tonStack[v] = false\n\t\t\t\tscc = append(scc, v)\n\t\t\t\tif v == u {\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t}\n\t\t\tsccs = append(sccs, scc)\n\t\t}\n\t}\n\n\tfor i := 0; i < n; i++ {\n\t\tif disc[i] == -1 {\n\t\t\tdfs(i)\n\t\t}\n\t}\n\treturn sccs\n}\n```\n\n\n \n\n\n```javascript\nfunction findSCCs(n, adj) {\n let timer = 0;\n const disc = new Array(n).fill(-1);\n const low = new Array(n).fill(-1);\n const onStack = new Array(n).fill(false);\n const stack = [];\n const sccs = [];\n\n function dfs(u) {\n disc[u] = low[u] = timer++;\n stack.push(u);\n onStack[u] = true;\n\n for (const v of adj[u]) {\n if (disc[v] === -1) {\n // v is unvisited, recurse\n dfs(v);\n low[u] = Math.min(low[u], low[v]);\n } else if (onStack[v]) {\n // v is on stack, part of current SCC\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n\n // If u is the root of an SCC\n if (disc[u] === low[u]) {\n const scc = [];\n while (true) {\n const v = stack.pop();\n onStack[v] = false;\n scc.push(v);\n if (v === u) break;\n }\n sccs.push(scc);\n }\n }\n\n for (let i = 0; i < n; i++) {\n if (disc[i] === -1) {\n dfs(i);\n }\n }\n return sccs;\n}\n```\n\n\n \n\n\n```typescript\nfunction findSCCs(n: number, adj: number[][]): number[][] {\n let timer = 0;\n const disc: number[] = new Array(n).fill(-1);\n const low: number[] = new Array(n).fill(-1);\n const onStack: boolean[] = new Array(n).fill(false);\n const stack: number[] = [];\n const sccs: number[][] = [];\n\n function dfs(u: number): void {\n disc[u] = low[u] = timer++;\n stack.push(u);\n onStack[u] = true;\n\n for (const v of adj[u]) {\n if (disc[v] === -1) {\n // v is unvisited, recurse\n dfs(v);\n low[u] = Math.min(low[u], low[v]);\n } else if (onStack[v]) {\n // v is on stack, part of current SCC\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n\n // If u is the root of an SCC\n if (disc[u] === low[u]) {\n const scc: number[] = [];\n while (true) {\n const v = stack.pop()!;\n onStack[v] = false;\n scc.push(v);\n if (v === u) break;\n }\n sccs.push(scc);\n }\n }\n\n for (let i = 0; i < n; i++) {\n if (disc[i] === -1) {\n dfs(i);\n }\n }\n return sccs;\n}\n```\n\n\n \n\nA few things to note about this implementation:\n\n- **disc[i] == -1** is used to check if vertex i is unvisited. This replaces the need for a separate visited[] array.\n- **onStack[]** is separate from the visited check. A vertex can be visited (disc != -1) but not on the stack if it has already been assigned to a completed SCC.\n- The time complexity is **O(V + E)** since every vertex and edge is processed exactly once during the DFS.\n- The space complexity is **O(V)** for the disc, low, onStack arrays and the stack.\n\n---\n\n## Step-by-Step Walkthrough\n\nLet us trace Tarjan's algorithm on a directed graph with 8 vertices and 3 SCCs.\n\n\n```mermaid\nflowchart LR\n 0:::primary --> 1:::primary\n 1 --> 2:::primary\n 2 --> 0\n 2 --> 3:::orange\n 3 --> 4:::orange\n 4 --> 5:::orange\n 5 --> 3\n 5 --> 6:::teal\n 6 --> 7:::teal\n 7 --> 6\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe three SCCs are: {0, 1, 2}, {3, 4, 5}, and {6, 7}. Let us see how the algorithm discovers them.\n\n**Step 1: Visit vertex 0**\n\n- disc[0] = 0, low[0] = 0\n- Stack: [0]\n- Recurse to neighbor 1.\n\n**Step 2: Visit vertex 1**\n\n- disc[1] = 1, low[1] = 1\n- Stack: [1, 0]\n- Recurse to neighbor 2.\n\n**Step 3: Visit vertex 2**\n\n- disc[2] = 2, low[2] = 2\n- Stack: [2, 1, 0]\n- Neighbor 0: already visited and on stack. low[2] = min(2, disc[0]) = min(2, 0) = 0.\n- Recurse to neighbor 3.\n\n**Step 4: Visit vertex 3**\n\n- disc[3] = 3, low[3] = 3\n- Stack: [3, 2, 1, 0]\n- Recurse to neighbor 4.\n\n**Step 5: Visit vertex 4**\n\n- disc[4] = 4, low[4] = 4\n- Stack: [4, 3, 2, 1, 0]\n- Recurse to neighbor 5.\n\n**Step 6: Visit vertex 5**\n\n- disc[5] = 5, low[5] = 5\n- Stack: [5, 4, 3, 2, 1, 0]\n- Neighbor 3: already visited and on stack. low[5] = min(5, disc[3]) = min(5, 3) = 3.\n- Recurse to neighbor 6.\n\n**Step 7: Visit vertex 6**\n\n- disc[6] = 6, low[6] = 6\n- Stack: [6, 5, 4, 3, 2, 1, 0]\n- Recurse to neighbor 7.\n\n**Step 8: Visit vertex 7**\n\n- disc[7] = 7, low[7] = 7\n- Stack: [7, 6, 5, 4, 3, 2, 1, 0]\n- Neighbor 6: already visited and on stack. low[7] = min(7, disc[6]) = min(7, 6) = 6.\n- All neighbors processed. disc[7] = 7, low[7] = 6. Not a root. Return.\n\n**Step 9: Back at vertex 6**\n\n- low[6] = min(low[6], low[7]) = min(6, 6) = 6.\n- All neighbors processed. disc[6] = 6, low[6] = 6. **Root found.**\n- Pop stack until 6: pop 7, pop 6. **SCC = {6, 7}**.\n- Stack: [5, 4, 3, 2, 1, 0]\n\n**Step 10: Back at vertex 5**\n\n- low[5] = min(low[5], low[6]). But 6 is no longer on stack, so this update does not apply (it was handled during step 6 already with the back edge to 3).\n- low[5] = 3.\n- All neighbors processed. disc[5] = 5, low[5] = 3. Not a root. Return.\n\n**Step 11: Back at vertex 4**\n\n- low[4] = min(low[4], low[5]) = min(4, 3) = 3.\n- All neighbors processed. disc[4] = 4, low[4] = 3. Not a root. Return.\n\n**Step 12: Back at vertex 3**\n\n- low[3] = min(low[3], low[4]) = min(3, 3) = 3.\n- All neighbors processed. disc[3] = 3, low[3] = 3. **Root found.**\n- Pop stack until 3: pop 5, pop 4, pop 3. **SCC = {3, 4, 5}**.\n- Stack: [2, 1, 0]\n\n**Step 13: Back at vertex 2**\n\n- low[2] = min(low[2], low[3]). But 3 is no longer on stack, so we keep low[2] = 0 from the back edge to vertex 0.\n- All neighbors processed. disc[2] = 2, low[2] = 0. Not a root. Return.\n\n**Step 14: Back at vertex 1**\n\n- low[1] = min(low[1], low[2]) = min(1, 0) = 0.\n- All neighbors processed. disc[1] = 1, low[1] = 0. Not a root. Return.\n\n**Step 15: Back at vertex 0**\n\n- low[0] = min(low[0], low[1]) = min(0, 0) = 0.\n- All neighbors processed. disc[0] = 0, low[0] = 0. **Root found.**\n- Pop stack until 0: pop 2, pop 1, pop 0. **SCC = {0, 1, 2}**.\n- Stack: []\n\nFinal state:\n\n\n| Vertex | disc | low | SCC |\n|--------|------|-----|-----|\n| 0 | 0 | 0 | {0, 1, 2} |\n| 1 | 1 | 0 | {0, 1, 2} |\n| 2 | 2 | 0 | {0, 1, 2} |\n| 3 | 3 | 3 | {3, 4, 5} |\n| 4 | 4 | 3 | {3, 4, 5} |\n| 5 | 5 | 3 | {3, 4, 5} |\n| 6 | 6 | 6 | {6, 7} |\n| 7 | 7 | 6 | {6, 7} |\n\n\nNotice the pattern: within each SCC, all vertices share the same low-link value, and that value equals the disc value of the SCC's root.\n\n---\n\n## Finding Bridges\n\nThe same disc and low values from Tarjan's algorithm can be used to find **bridges** in an undirected graph. A bridge is an edge whose removal disconnects the graph (or increases the number of connected components).\n\nAn edge (u, v) is a bridge if **low[v] > disc[u]**. This condition means that vertex v has no way to reach u or any ancestor of u without using the edge (u, v). Removing that edge would therefore disconnect v's subtree from the rest of the graph.\n\n\n```mermaid\nflowchart LR\n A[\"0\"]:::primary --- B[\"1\"]:::primary\n B --- C[\"2\"]:::primary\n C --- A\n C -. \"Bridge\" .- D[\"3\"]:::red\n D --- E[\"4\"]:::orange\n E --- D\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n\n linkStyle 3 stroke:#ff0000,stroke-width:3px\n```\n\n\nIn this graph, the edge (2, 3) is a bridge. Vertices {0, 1, 2} form a cycle, so removing any edge between them still keeps them connected. But the only way to reach vertex 3 from vertices {0, 1, 2} is through that single edge.\n\nHere is the implementation for finding bridges:\n\n \n\n\n```java\nimport java.util.*;\n\npublic class Bridges {\n private int timer = 0;\n private int[] disc;\n private int[] low;\n private List> adj;\n private List bridges;\n\n public List findBridges(int n, List> adj) {\n this.adj = adj;\n disc = new int[n];\n low = new int[n];\n bridges = new ArrayList<>();\n Arrays.fill(disc, -1);\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n dfs(i, -1);\n }\n }\n return bridges;\n }\n\n private void dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n\n for (int v : adj.get(u)) {\n if (v == parent) continue; // skip the edge back to parent\n if (disc[v] == -1) {\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n if (low[v] > disc[u]) {\n bridges.add(new int[]{u, v});\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n }\n}\n```\n\n\n \n\n\n```python\nclass Bridges:\n def __init__(self):\n self.timer = 0\n self.disc: list[int] = []\n self.low: list[int] = []\n self.adj: list[list[int]] = []\n self.bridges: list[tuple[int, int]] = []\n\n def find_bridges(self, n: int, adj: list[list[int]]) -> list[tuple[int, int]]:\n self.adj = adj\n self.disc = [-1] * n\n self.low = [-1] * n\n self.bridges = []\n self.timer = 0\n\n for i in range(n):\n if self.disc[i] == -1:\n self._dfs(i, -1)\n return self.bridges\n\n def _dfs(self, u: int, parent: int) -> None:\n self.disc[u] = self.low[u] = self.timer\n self.timer += 1\n\n for v in self.adj[u]:\n if v == parent:\n continue # skip the edge back to parent\n if self.disc[v] == -1:\n self._dfs(v, u)\n self.low[u] = min(self.low[u], self.low[v])\n if self.low[v] > self.disc[u]:\n self.bridges.append((u, v))\n else:\n self.low[u] = min(self.low[u], self.disc[v])\n```\n\n\n \n\n\n```cpp\n#include \n#include \nusing namespace std;\n\nclass Bridges {\n int timer = 0;\n vector disc, low;\n vector>& adj;\n vector> bridges;\n\n void dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n\n for (int v : adj[u]) {\n if (v == parent) continue; // skip the edge back to parent\n if (disc[v] == -1) {\n dfs(v, u);\n low[u] = min(low[u], low[v]);\n if (low[v] > disc[u]) {\n bridges.push_back({u, v});\n }\n } else {\n low[u] = min(low[u], disc[v]);\n }\n }\n }\n\npublic:\n Bridges(vector>& adjacency) : adj(adjacency) {}\n\n vector> findBridges(int n) {\n disc.assign(n, -1);\n low.assign(n, -1);\n bridges.clear();\n timer = 0;\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n dfs(i, -1);\n }\n }\n return bridges;\n }\n};\n```\n\n\n \n\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\npublic class Bridges {\n private int timer = 0;\n private int[] disc;\n private int[] low;\n private List> adj;\n private List bridges;\n\n public List FindBridges(int n, List> adj) {\n this.adj = adj;\n disc = new int[n];\n low = new int[n];\n bridges = new List();\n Array.Fill(disc, -1);\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n Dfs(i, -1);\n }\n }\n return bridges;\n }\n\n private void Dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n\n foreach (int v in adj[u]) {\n if (v == parent) continue; // skip the edge back to parent\n if (disc[v] == -1) {\n Dfs(v, u);\n low[u] = Math.Min(low[u], low[v]);\n if (low[v] > disc[u]) {\n bridges.Add(new int[] { u, v });\n }\n } else {\n low[u] = Math.Min(low[u], disc[v]);\n }\n }\n }\n}\n```\n\n\n \n\n\n```go\npackage tarjan\n\nfunc FindBridges(n int, adj [][]int) [][2]int {\n\ttimer := 0\n\tdisc := make([]int, n)\n\tlow := make([]int, n)\n\tbridges := [][2]int{}\n\n\tfor i := range disc {\n\t\tdisc[i] = -1\n\t}\n\n\tvar dfs func(u, parent int)\n\tdfs = func(u, parent int) {\n\t\tdisc[u] = timer\n\t\tlow[u] = timer\n\t\ttimer++\n\n\t\tfor _, v := range adj[u] {\n\t\t\tif v == parent {\n\t\t\t\tcontinue // skip the edge back to parent\n\t\t\t}\n\t\t\tif disc[v] == -1 {\n\t\t\t\tdfs(v, u)\n\t\t\t\tif low[v] < low[u] {\n\t\t\t\t\tlow[u] = low[v]\n\t\t\t\t}\n\t\t\t\tif low[v] > disc[u] {\n\t\t\t\t\tbridges = append(bridges, [2]int{u, v})\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tif disc[v] < low[u] {\n\t\t\t\t\tlow[u] = disc[v]\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\tfor i := 0; i < n; i++ {\n\t\tif disc[i] == -1 {\n\t\t\tdfs(i, -1)\n\t\t}\n\t}\n\treturn bridges\n}\n```\n\n\n \n\n\n```javascript\nfunction findBridges(n, adj) {\n let timer = 0;\n const disc = new Array(n).fill(-1);\n const low = new Array(n).fill(-1);\n const bridges = [];\n\n function dfs(u, parent) {\n disc[u] = low[u] = timer++;\n\n for (const v of adj[u]) {\n if (v === parent) continue; // skip the edge back to parent\n if (disc[v] === -1) {\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n if (low[v] > disc[u]) {\n bridges.push([u, v]);\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n }\n\n for (let i = 0; i < n; i++) {\n if (disc[i] === -1) {\n dfs(i, -1);\n }\n }\n return bridges;\n}\n```\n\n\n \n\n\n```typescript\nfunction findBridges(n: number, adj: number[][]): [number, number][] {\n let timer = 0;\n const disc: number[] = new Array(n).fill(-1);\n const low: number[] = new Array(n).fill(-1);\n const bridges: [number, number][] = [];\n\n function dfs(u: number, parent: number): void {\n disc[u] = low[u] = timer++;\n\n for (const v of adj[u]) {\n if (v === parent) continue; // skip the edge back to parent\n if (disc[v] === -1) {\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n if (low[v] > disc[u]) {\n bridges.push([u, v]);\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n }\n\n for (let i = 0; i < n; i++) {\n if (disc[i] === -1) {\n dfs(i, -1);\n }\n }\n return bridges;\n}\n```\n\n\n \n\nKey differences from the SCC version:\n\n- This works on **undirected** graphs, so we skip the parent edge to avoid treating it as a back edge.\n- There is no stack. We do not need to track SCCs, just detect the bridge condition.\n- The bridge check happens after the recursive call: if low[v] > disc[u], edge (u, v) is a bridge.\n\n**Interview Insight:** The bridge condition is low[v] > disc[u] (strictly greater). Do not confuse this with the articulation point condition, which uses >=. The difference is subtle but important.\n\n---\n\n## Finding Articulation Points\n\nAn **articulation point** (or cut vertex) is a vertex whose removal disconnects the graph. The logic is similar to finding bridges but with a slightly different condition.\n\nA vertex u is an articulation point if either:\n\n1. **u is the root of the DFS tree** and has **two or more children** in the DFS tree. If the root has only one child, removing it does not disconnect anything because the entire graph is in that one subtree.\n\n1. **u is not the root** and there exists a child v such that **low[v] >= disc[u]**. This means no vertex in v's subtree can reach an ancestor of u without going through u.\n\n\n```mermaid\nflowchart LR\n A[\"0\"]:::primary --- B[\"1\"]:::green\n B --- C[\"2\"]:::primary\n C --- A\n B --- D[\"3\"]:::primary\n D --- E[\"4\"]:::primary\n E --- D\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nIn this graph, vertex 1 is an articulation point. Remove it, and {0, 2} gets disconnected from {3, 4}.\n\nHere is the implementation for finding articulation points:\n\n \n\n\n```java\nimport java.util.*;\n\npublic class ArticulationPoints {\n private int timer = 0;\n private int[] disc;\n private int[] low;\n private List> adj;\n private Set articulationPoints;\n\n public Set findArticulationPoints(int n, List> adj) {\n this.adj = adj;\n disc = new int[n];\n low = new int[n];\n articulationPoints = new HashSet<>();\n Arrays.fill(disc, -1);\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n dfs(i, -1);\n }\n }\n return articulationPoints;\n }\n\n private void dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n int childCount = 0;\n\n for (int v : adj.get(u)) {\n if (v == parent) continue;\n if (disc[v] == -1) {\n childCount++;\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n\n // Non-root with a child that can't reach above u\n if (parent != -1 && low[v] >= disc[u]) {\n articulationPoints.add(u);\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n\n // Root with 2+ children in DFS tree\n if (parent == -1 && childCount > 1) {\n articulationPoints.add(u);\n }\n }\n}\n```\n\n\n \n\n\n```python\nclass ArticulationPoints:\n def __init__(self):\n self.timer = 0\n self.disc: list[int] = []\n self.low: list[int] = []\n self.adj: list[list[int]] = []\n self.articulation_points: set[int] = set()\n\n def find_articulation_points(self, n: int, adj: list[list[int]]) -> set[int]:\n self.adj = adj\n self.disc = [-1] * n\n self.low = [-1] * n\n self.articulation_points = set()\n self.timer = 0\n\n for i in range(n):\n if self.disc[i] == -1:\n self._dfs(i, -1)\n return self.articulation_points\n\n def _dfs(self, u: int, parent: int) -> None:\n self.disc[u] = self.low[u] = self.timer\n self.timer += 1\n child_count = 0\n\n for v in self.adj[u]:\n if v == parent:\n continue\n if self.disc[v] == -1:\n child_count += 1\n self._dfs(v, u)\n self.low[u] = min(self.low[u], self.low[v])\n\n # Non-root with a child that can't reach above u\n if parent != -1 and self.low[v] >= self.disc[u]:\n self.articulation_points.add(u)\n else:\n self.low[u] = min(self.low[u], self.disc[v])\n\n # Root with 2+ children in DFS tree\n if parent == -1 and child_count > 1:\n self.articulation_points.add(u)\n```\n\n\n \n\n\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\nclass ArticulationPoints {\n int timer = 0;\n vector disc, low;\n vector>& adj;\n set articulationPoints;\n\n void dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n int childCount = 0;\n\n for (int v : adj[u]) {\n if (v == parent) continue;\n if (disc[v] == -1) {\n childCount++;\n dfs(v, u);\n low[u] = min(low[u], low[v]);\n\n // Non-root with a child that can't reach above u\n if (parent != -1 && low[v] >= disc[u]) {\n articulationPoints.insert(u);\n }\n } else {\n low[u] = min(low[u], disc[v]);\n }\n }\n\n // Root with 2+ children in DFS tree\n if (parent == -1 && childCount > 1) {\n articulationPoints.insert(u);\n }\n }\n\npublic:\n ArticulationPoints(vector>& adjacency) : adj(adjacency) {}\n\n set findArticulationPoints(int n) {\n disc.assign(n, -1);\n low.assign(n, -1);\n articulationPoints.clear();\n timer = 0;\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n dfs(i, -1);\n }\n }\n return articulationPoints;\n }\n};\n```\n\n\n \n\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\npublic class ArticulationPoints {\n private int timer = 0;\n private int[] disc;\n private int[] low;\n private List> adj;\n private HashSet articulationPoints;\n\n public HashSet FindArticulationPoints(int n, List> adj) {\n this.adj = adj;\n disc = new int[n];\n low = new int[n];\n articulationPoints = new HashSet();\n Array.Fill(disc, -1);\n\n for (int i = 0; i < n; i++) {\n if (disc[i] == -1) {\n Dfs(i, -1);\n }\n }\n return articulationPoints;\n }\n\n private void Dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n int childCount = 0;\n\n foreach (int v in adj[u]) {\n if (v == parent) continue;\n if (disc[v] == -1) {\n childCount++;\n Dfs(v, u);\n low[u] = Math.Min(low[u], low[v]);\n\n // Non-root with a child that can't reach above u\n if (parent != -1 && low[v] >= disc[u]) {\n articulationPoints.Add(u);\n }\n } else {\n low[u] = Math.Min(low[u], disc[v]);\n }\n }\n\n // Root with 2+ children in DFS tree\n if (parent == -1 && childCount > 1) {\n articulationPoints.Add(u);\n }\n }\n}\n```\n\n\n \n\n\n```go\npackage tarjan\n\nfunc FindArticulationPoints(n int, adj [][]int) map[int]bool {\n\ttimer := 0\n\tdisc := make([]int, n)\n\tlow := make([]int, n)\n\tarticulationPoints := map[int]bool{}\n\n\tfor i := range disc {\n\t\tdisc[i] = -1\n\t}\n\n\tvar dfs func(u, parent int)\n\tdfs = func(u, parent int) {\n\t\tdisc[u] = timer\n\t\tlow[u] = timer\n\t\ttimer++\n\t\tchildCount := 0\n\n\t\tfor _, v := range adj[u] {\n\t\t\tif v == parent {\n\t\t\t\tcontinue\n\t\t\t}\n\t\t\tif disc[v] == -1 {\n\t\t\t\tchildCount++\n\t\t\t\tdfs(v, u)\n\t\t\t\tif low[v] < low[u] {\n\t\t\t\t\tlow[u] = low[v]\n\t\t\t\t}\n\n\t\t\t\t// Non-root with a child that can't reach above u\n\t\t\t\tif parent != -1 && low[v] >= disc[u] {\n\t\t\t\t\tarticulationPoints[u] = true\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tif disc[v] < low[u] {\n\t\t\t\t\tlow[u] = disc[v]\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\t// Root with 2+ children in DFS tree\n\t\tif parent == -1 && childCount > 1 {\n\t\t\tarticulationPoints[u] = true\n\t\t}\n\t}\n\n\tfor i := 0; i < n; i++ {\n\t\tif disc[i] == -1 {\n\t\t\tdfs(i, -1)\n\t\t}\n\t}\n\treturn articulationPoints\n}\n```\n\n\n \n\n\n```javascript\nfunction findArticulationPoints(n, adj) {\n let timer = 0;\n const disc = new Array(n).fill(-1);\n const low = new Array(n).fill(-1);\n const articulationPoints = new Set();\n\n function dfs(u, parent) {\n disc[u] = low[u] = timer++;\n let childCount = 0;\n\n for (const v of adj[u]) {\n if (v === parent) continue;\n if (disc[v] === -1) {\n childCount++;\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n\n // Non-root with a child that can't reach above u\n if (parent !== -1 && low[v] >= disc[u]) {\n articulationPoints.add(u);\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n\n // Root with 2+ children in DFS tree\n if (parent === -1 && childCount > 1) {\n articulationPoints.add(u);\n }\n }\n\n for (let i = 0; i < n; i++) {\n if (disc[i] === -1) {\n dfs(i, -1);\n }\n }\n return articulationPoints;\n}\n```\n\n\n \n\n\n```typescript\nfunction findArticulationPoints(n: number, adj: number[][]): Set {\n let timer = 0;\n const disc: number[] = new Array(n).fill(-1);\n const low: number[] = new Array(n).fill(-1);\n const articulationPoints = new Set();\n\n function dfs(u: number, parent: number): void {\n disc[u] = low[u] = timer++;\n let childCount = 0;\n\n for (const v of adj[u]) {\n if (v === parent) continue;\n if (disc[v] === -1) {\n childCount++;\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n\n // Non-root with a child that can't reach above u\n if (parent !== -1 && low[v] >= disc[u]) {\n articulationPoints.add(u);\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n\n // Root with 2+ children in DFS tree\n if (parent === -1 && childCount > 1) {\n articulationPoints.add(u);\n }\n }\n\n for (let i = 0; i < n; i++) {\n if (disc[i] === -1) {\n dfs(i, -1);\n }\n }\n return articulationPoints;\n}\n```\n\n\n \n\nUsing a set for articulation points avoids duplicates, since a vertex might satisfy the condition for multiple children.\n\n**Interview Insight:** The two cases for articulation points (root vs non-root) are a common follow-up question. Make sure you can explain why the root needs a separate check. The root has no ancestors, so the low[v] >= disc[u] condition alone is not sufficient.\n\n---\n\n## Example Problem: Critical Connections in a Network\n\n**LeetCode 1192 - Critical Connections in a Network**\n\nThere are n servers numbered from 0 to n-1 connected by undirected edges given as connections[i] = [a, b]. A critical connection is an edge that, if removed, would make some server unable to reach another server. Find all critical connections.\n\nThis is exactly the bridge-finding problem. We apply Tarjan's algorithm to find all edges (u, v) where low[v] > disc[u].\n\n \n\n\n```java\nclass Solution {\n private int timer = 0;\n private int[] disc;\n private int[] low;\n private List> adj;\n private List> result;\n\n public List> criticalConnections(int n,\n List> connections) {\n adj = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n adj.add(new ArrayList<>());\n }\n for (List conn : connections) {\n adj.get(conn.get(0)).add(conn.get(1));\n adj.get(conn.get(1)).add(conn.get(0));\n }\n\n disc = new int[n];\n low = new int[n];\n result = new ArrayList<>();\n Arrays.fill(disc, -1);\n\n dfs(0, -1);\n return result;\n }\n\n private void dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n\n for (int v : adj.get(u)) {\n if (v == parent) continue;\n if (disc[v] == -1) {\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n if (low[v] > disc[u]) {\n result.add(Arrays.asList(u, v));\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n }\n}\n```\n\n\n \n\n\n```python\nclass Solution:\n def criticalConnections(self, n: int, connections: list[list[int]]) -> list[list[int]]:\n adj: list[list[int]] = [[] for _ in range(n)]\n for a, b in connections:\n adj[a].append(b)\n adj[b].append(a)\n\n disc = [-1] * n\n low = [-1] * n\n result: list[list[int]] = []\n timer = [0]\n\n def dfs(u: int, parent: int) -> None:\n disc[u] = low[u] = timer[0]\n timer[0] += 1\n\n for v in adj[u]:\n if v == parent:\n continue\n if disc[v] == -1:\n dfs(v, u)\n low[u] = min(low[u], low[v])\n if low[v] > disc[u]:\n result.append([u, v])\n else:\n low[u] = min(low[u], disc[v])\n\n dfs(0, -1)\n return result\n```\n\n\n \n\n\n```cpp\n#include \n#include \nusing namespace std;\n\nclass Solution {\n int timer = 0;\n vector disc, low;\n vector> adj;\n vector> result;\n\n void dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n\n for (int v : adj[u]) {\n if (v == parent) continue;\n if (disc[v] == -1) {\n dfs(v, u);\n low[u] = min(low[u], low[v]);\n if (low[v] > disc[u]) {\n result.push_back({u, v});\n }\n } else {\n low[u] = min(low[u], disc[v]);\n }\n }\n }\n\npublic:\n vector> criticalConnections(int n,\n vector>& connections) {\n adj.assign(n, vector());\n for (auto& conn : connections) {\n adj[conn[0]].push_back(conn[1]);\n adj[conn[1]].push_back(conn[0]);\n }\n\n disc.assign(n, -1);\n low.assign(n, -1);\n result.clear();\n\n dfs(0, -1);\n return result;\n }\n};\n```\n\n\n \n\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\npublic class Solution {\n private int timer = 0;\n private int[] disc;\n private int[] low;\n private List> adj;\n private IList> result;\n\n public IList> CriticalConnections(int n,\n IList> connections) {\n adj = new List>();\n for (int i = 0; i < n; i++) {\n adj.Add(new List());\n }\n foreach (var conn in connections) {\n adj[conn[0]].Add(conn[1]);\n adj[conn[1]].Add(conn[0]);\n }\n\n disc = new int[n];\n low = new int[n];\n result = new List>();\n Array.Fill(disc, -1);\n\n Dfs(0, -1);\n return result;\n }\n\n private void Dfs(int u, int parent) {\n disc[u] = low[u] = timer++;\n\n foreach (int v in adj[u]) {\n if (v == parent) continue;\n if (disc[v] == -1) {\n Dfs(v, u);\n low[u] = Math.Min(low[u], low[v]);\n if (low[v] > disc[u]) {\n result.Add(new List { u, v });\n }\n } else {\n low[u] = Math.Min(low[u], disc[v]);\n }\n }\n }\n}\n```\n\n\n \n\n\n```go\nfunc criticalConnections(n int, connections [][]int) [][]int {\n\tadj := make([][]int, n)\n\tfor _, conn := range connections {\n\t\tadj[conn[0]] = append(adj[conn[0]], conn[1])\n\t\tadj[conn[1]] = append(adj[conn[1]], conn[0])\n\t}\n\n\ttimer := 0\n\tdisc := make([]int, n)\n\tlow := make([]int, n)\n\tresult := [][]int{}\n\n\tfor i := range disc {\n\t\tdisc[i] = -1\n\t}\n\n\tvar dfs func(u, parent int)\n\tdfs = func(u, parent int) {\n\t\tdisc[u] = timer\n\t\tlow[u] = timer\n\t\ttimer++\n\n\t\tfor _, v := range adj[u] {\n\t\t\tif v == parent {\n\t\t\t\tcontinue\n\t\t\t}\n\t\t\tif disc[v] == -1 {\n\t\t\t\tdfs(v, u)\n\t\t\t\tif low[v] < low[u] {\n\t\t\t\t\tlow[u] = low[v]\n\t\t\t\t}\n\t\t\t\tif low[v] > disc[u] {\n\t\t\t\t\tresult = append(result, []int{u, v})\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tif disc[v] < low[u] {\n\t\t\t\t\tlow[u] = disc[v]\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\tdfs(0, -1)\n\treturn result\n}\n```\n\n\n \n\n\n```javascript\nvar criticalConnections = function(n, connections) {\n const adj = Array.from({ length: n }, () => []);\n for (const [a, b] of connections) {\n adj[a].push(b);\n adj[b].push(a);\n }\n\n let timer = 0;\n const disc = new Array(n).fill(-1);\n const low = new Array(n).fill(-1);\n const result = [];\n\n function dfs(u, parent) {\n disc[u] = low[u] = timer++;\n\n for (const v of adj[u]) {\n if (v === parent) continue;\n if (disc[v] === -1) {\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n if (low[v] > disc[u]) {\n result.push([u, v]);\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n }\n\n dfs(0, -1);\n return result;\n};\n```\n\n\n \n\n\n```typescript\nfunction criticalConnections(n: number, connections: number[][]): number[][] {\n const adj: number[][] = Array.from({ length: n }, () => []);\n for (const [a, b] of connections) {\n adj[a].push(b);\n adj[b].push(a);\n }\n\n let timer = 0;\n const disc: number[] = new Array(n).fill(-1);\n const low: number[] = new Array(n).fill(-1);\n const result: number[][] = [];\n\n function dfs(u: number, parent: number): void {\n disc[u] = low[u] = timer++;\n\n for (const v of adj[u]) {\n if (v === parent) continue;\n if (disc[v] === -1) {\n dfs(v, u);\n low[u] = Math.min(low[u], low[v]);\n if (low[v] > disc[u]) {\n result.push([u, v]);\n }\n } else {\n low[u] = Math.min(low[u], disc[v]);\n }\n }\n }\n\n dfs(0, -1);\n return result;\n}\n```\n\n\n \n\n**Time Complexity:** O(V + E). Each vertex and edge is visited exactly once.\n\n**Space Complexity:** O(V + E) for the adjacency list and O(V) for the disc, low arrays and recursion stack.\n\nThis problem is a direct application of bridge finding, no modifications needed. In an interview, the hardest part is recognizing that \"critical connections\" are bridges and then applying the algorithm cleanly.\n\n---\n\n## Tarjan's vs Kosaraju's\n\nBoth algorithms find strongly connected components in O(V + E) time, but they take different approaches.\n\n\n| Aspect | Tarjan's | Kosaraju's |\n|--------|----------|------------|\n| Number of DFS passes | 1 | 2 |\n| Needs graph reversal | No | Yes |\n| Extra data structures | Stack + disc/low arrays | Stack + reversed graph |\n| Space overhead | O(V) | O(V + E) for reversed graph |\n| Conceptual complexity | Higher | Lower |\n| Output order | Reverse topological order | Topological order |\n| Handles undirected graphs | With modifications (bridges, APs) | Not directly |\n\n\n**When to prefer Tarjan's:**\n\n- When memory is tight (no need to store the reversed graph).\n- When you also need bridges or articulation points (same core idea).\n- When you want everything done in a single pass.\n\n**When to prefer Kosaraju's:**\n\n- When you want a simpler implementation that is easier to get right under interview pressure.\n- When topological order of SCCs matters directly (Kosaraju gives this naturally).\n- When you are already comfortable with its two-pass structure.\n\nIn practice, both algorithms are interchangeable for finding SCCs. Tarjan's is more elegant but harder to implement correctly. Kosaraju's is more straightforward but needs extra space for the reversed graph.\n\n**Interview Insight:** If an interviewer asks you to compare the two, focus on the trade-offs. Mentioning that Tarjan's is a single-pass algorithm while Kosaraju's needs two passes and a graph reversal demonstrates solid understanding.\n\n---\n\n## Common Mistakes\n\nThese are the pitfalls that catch people most often when implementing Tarjan's algorithm.\n\n### 1. Confusing disc and low\n\nThe discovery time (disc) is set once and never changes. The low-link value (low) gets updated as you discover back edges and process recursive returns. A common mistake is updating disc instead of low, or initializing low incorrectly.\n\n \n\n\n```java\n// WRONG: updating disc instead of low\ndisc[u] = Math.min(disc[u], disc[v]); // disc should never change\n\n// CORRECT: updating low\nlow[u] = Math.min(low[u], disc[v]);\n```\n\n\n \n\n\n```python\n# WRONG: updating disc instead of low\ndisc[u] = min(disc[u], disc[v]) # disc should never change\n\n# CORRECT: updating low\nlow[u] = min(low[u], disc[v])\n```\n\n\n \n\n\n```cpp\n// WRONG: updating disc instead of low\ndisc[u] = min(disc[u], disc[v]); // disc should never change\n\n// CORRECT: updating low\nlow[u] = min(low[u], disc[v]);\n```\n\n\n \n\n\n```csharp\n// WRONG: updating disc instead of low\ndisc[u] = Math.Min(disc[u], disc[v]); // disc should never change\n\n// CORRECT: updating low\nlow[u] = Math.Min(low[u], disc[v]);\n```\n\n\n \n\n\n```go\n// WRONG: updating disc instead of low\nif disc[v] < disc[u] { disc[u] = disc[v] } // disc should never change\n\n// CORRECT: updating low\nif disc[v] < low[u] { low[u] = disc[v] }\n```\n\n\n \n\n\n```javascript\n// WRONG: updating disc instead of low\ndisc[u] = Math.min(disc[u], disc[v]); // disc should never change\n\n// CORRECT: updating low\nlow[u] = Math.min(low[u], disc[v]);\n```\n\n\n \n\n\n```typescript\n// WRONG: updating disc instead of low\ndisc[u] = Math.min(disc[u], disc[v]); // disc should never change\n\n// CORRECT: updating low\nlow[u] = Math.min(low[u], disc[v]);\n```\n\n\n \n\n### 2. Updating low-link from vertices not on the stack\n\nWhen finding SCCs, you should only update low[u] from a neighbor v if v is currently on the stack. If v was already assigned to a completed SCC, using its disc or low value would incorrectly merge two separate SCCs.\n\n \n\n\n```java\n// WRONG: updating from any visited vertex\nif (disc[v] != -1) {\n low[u] = Math.min(low[u], disc[v]); // v might be in a finished SCC\n}\n\n// CORRECT: only update if v is on the stack\nif (disc[v] != -1 && onStack[v]) {\n low[u] = Math.min(low[u], disc[v]);\n}\n```\n\n\n \n\n\n```python\n# WRONG: updating from any visited vertex\nif disc[v] != -1:\n low[u] = min(low[u], disc[v]) # v might be in a finished SCC\n\n# CORRECT: only update if v is on the stack\nif disc[v] != -1 and on_stack[v]:\n low[u] = min(low[u], disc[v])\n```\n\n\n \n\n\n```cpp\n// WRONG: updating from any visited vertex\nif (disc[v] != -1) {\n low[u] = min(low[u], disc[v]); // v might be in a finished SCC\n}\n\n// CORRECT: only update if v is on the stack\nif (disc[v] != -1 && onStack[v]) {\n low[u] = min(low[u], disc[v]);\n}\n```\n\n\n \n\n\n```csharp\n// WRONG: updating from any visited vertex\nif (disc[v] != -1) {\n low[u] = Math.Min(low[u], disc[v]); // v might be in a finished SCC\n}\n\n// CORRECT: only update if v is on the stack\nif (disc[v] != -1 && onStack[v]) {\n low[u] = Math.Min(low[u], disc[v]);\n}\n```\n\n\n \n\n\n```go\n// WRONG: updating from any visited vertex\nif disc[v] != -1 {\n if disc[v] < low[u] { low[u] = disc[v] } // v might be in a finished SCC\n}\n\n// CORRECT: only update if v is on the stack\nif disc[v] != -1 && onStack[v] {\n if disc[v] < low[u] { low[u] = disc[v] }\n}\n```\n\n\n \n\n\n```javascript\n// WRONG: updating from any visited vertex\nif (disc[v] !== -1) {\n low[u] = Math.min(low[u], disc[v]); // v might be in a finished SCC\n}\n\n// CORRECT: only update if v is on the stack\nif (disc[v] !== -1 && onStack[v]) {\n low[u] = Math.min(low[u], disc[v]);\n}\n```\n\n\n \n\n\n```typescript\n// WRONG: updating from any visited vertex\nif (disc[v] !== -1) {\n low[u] = Math.min(low[u], disc[v]); // v might be in a finished SCC\n}\n\n// CORRECT: only update if v is on the stack\nif (disc[v] !== -1 && onStack[v]) {\n low[u] = Math.min(low[u], disc[v]);\n}\n```\n\n\n \n\n### 3. Forgetting the parent check for undirected graphs\n\nWhen finding bridges or articulation points in undirected graphs, you must skip the edge back to the parent. Otherwise, every edge looks like a back edge, and the algorithm produces wrong results.\n\n \n\n\n```java\n// WRONG: no parent check\nfor (int v : adj.get(u)) {\n if (disc[v] == -1) { ... }\n else { low[u] = Math.min(low[u], disc[v]); } // treats parent as back edge\n}\n\n// CORRECT: skip the parent\nfor (int v : adj.get(u)) {\n if (v == parent) continue;\n // ...\n}\n```\n\n\n \n\n\n```python\n# WRONG: no parent check\nfor v in adj[u]:\n if disc[v] == -1: ...\n else: low[u] = min(low[u], disc[v]) # treats parent as back edge\n\n# CORRECT: skip the parent\nfor v in adj[u]:\n if v == parent:\n continue\n # ...\n```\n\n\n \n\n\n```cpp\n// WRONG: no parent check\nfor (int v : adj[u]) {\n if (disc[v] == -1) { ... }\n else { low[u] = min(low[u], disc[v]); } // treats parent as back edge\n}\n\n// CORRECT: skip the parent\nfor (int v : adj[u]) {\n if (v == parent) continue;\n // ...\n}\n```\n\n\n \n\n\n```csharp\n// WRONG: no parent check\nforeach (int v in adj[u]) {\n if (disc[v] == -1) { ... }\n else { low[u] = Math.Min(low[u], disc[v]); } // treats parent as back edge\n}\n\n// CORRECT: skip the parent\nforeach (int v in adj[u]) {\n if (v == parent) continue;\n // ...\n}\n```\n\n\n \n\n\n```go\n// WRONG: no parent check\nfor _, v := range adj[u] {\n if disc[v] == -1 { ... }\n // treats parent as back edge\n}\n\n// CORRECT: skip the parent\nfor _, v := range adj[u] {\n if v == parent { continue }\n // ...\n}\n```\n\n\n \n\n\n```javascript\n// WRONG: no parent check\nfor (const v of adj[u]) {\n if (disc[v] === -1) { ... }\n else { low[u] = Math.min(low[u], disc[v]); } // treats parent as back edge\n}\n\n// CORRECT: skip the parent\nfor (const v of adj[u]) {\n if (v === parent) continue;\n // ...\n}\n```\n\n\n \n\n\n```typescript\n// WRONG: no parent check\nfor (const v of adj[u]) {\n if (disc[v] === -1) { ... }\n else { low[u] = Math.min(low[u], disc[v]); } // treats parent as back edge\n}\n\n// CORRECT: skip the parent\nfor (const v of adj[u]) {\n if (v === parent) continue;\n // ...\n}\n```\n\n\n \n\n### 4. Not handling parallel edges correctly\n\nIf the graph has multiple edges between the same pair of vertices, the simple `v == parent` check is not sufficient. You should track the edge index or use a counter to handle this correctly.\n\n### 5. Mixing up bridge and articulation point conditions\n\n- **Bridge:** low[v] > disc[u] (strictly greater)\n- **Articulation point:** low[v] >= disc[u] (greater than or equal)\n\nThe difference matters. For a bridge, vertex v must have absolutely no alternative path to u or above. For an articulation point, even if v can reach u through another path, removing u still disconnects v's subtree because v can only reach u, not u's ancestors.\n\n---\n\n## Interview Questions\n\n**Q1: What is the time and space complexity of Tarjan's algorithm?**\n\nTime complexity is O(V + E) because each vertex is visited exactly once during DFS and each edge is examined once. Space complexity is O(V) for the disc, low, and onStack arrays plus the explicit stack. The recursion stack can also go up to O(V) in the worst case for a linear graph.\n\n**Q2: Can Tarjan's algorithm work on undirected graphs?**\n\nThe SCC version of Tarjan's is designed for directed graphs. In undirected graphs, every edge creates a trivial cycle (you can go back and forth), so every connected component is trivially strongly connected. However, the same disc/low technique extends naturally to undirected graphs for finding bridges and articulation points, which is actually more common in practice.\n\n**Q3: What happens if the graph is disconnected?**\n\nTarjan's handles disconnected graphs by iterating over all vertices and starting a new DFS from any unvisited vertex. This is the outer loop in the implementation that checks each vertex and calls DFS if it has not been visited yet. Each connected portion of the graph gets processed independently.\n\n**Q4: How does the stack differ from the recursion call stack in Tarjan's algorithm?**\n\nThe recursion call stack tracks the current DFS path. The explicit stack in Tarjan's algorithm holds all vertices that have been visited but not yet assigned to an SCC. These are different. A vertex stays on the explicit stack even after its DFS call returns, as long as it has not been identified as part of a completed SCC. It only gets removed when its SCC root is found and the component is popped off.\n\n**Q5: Why do we use disc[v] instead of low[v] when updating low[u] from a vertex already on the stack?**\n\nBoth approaches produce correct results for finding SCCs. Using disc[v] is the version from Tarjan's original paper. The reasoning is that for a vertex already on the stack, we want to record that u can reach as far back as v was discovered, not wherever v can reach. Using low[v] also works, but using disc[v] keeps the invariant cleaner and avoids potential issues in certain edge cases.\n\n---\n\n## Summary\n\nTarjan's algorithm is a single-pass DFS that finds all strongly connected components in a directed graph in O(V + E) time. The key ideas are:\n\n- **Discovery time** timestamps when each vertex is first visited.\n- **Low-link value** tracks the earliest discoverable vertex reachable from the current vertex.\n- A vertex is the **root of an SCC** when disc[u] == low[u], meaning it cannot reach anything discovered earlier.\n- The same disc/low framework extends to finding **bridges** (low[v] > disc[u]) and **articulation points** (low[v] >= disc[u]) in undirected graphs.\n- Compared to Kosaraju's, Tarjan's uses a single pass and does not require reversing the graph, but is slightly harder to implement correctly.\n\nThe numbers to remember: O(V + E) time, O(V) space, single DFS pass.\n\nIn the next chapter, we will look at more advanced graph algorithms that build on these concepts.\n\n---\n\n## References\n\n- [Tarjan's Algorithm - Wikipedia](undefined)\n- [Strongly Connected Components - CP-Algorithms](undefined)\n- [Bridges and Articulation Points - CP-Algorithms](undefined)\n- [LeetCode 1192 - Critical Connections in a Network](undefined)\n- [Introduction to Algorithms (CLRS), Chapter 22: Elementary Graph Algorithms](undefined)","pageType":"dsa"}

Tarjan's Algorithm

Ashish Pratap Singh

Get Premium