{"title":"Kosaraju's Algorithm","description":"","content":"Think about the web. You can get from page A to page B through a chain of hyperlinks, and from page B back to page A through a different chain. These two pages, along with every other page mutually reachable in both directions, form a tightly knit cluster. In 2000, a famous study called the \"Bowtie Model\" revealed that the web has one massive cluster like this containing roughly 30% of all indexed pages, surrounded by pages that can reach it but not be reached from it, and vice versa.\n\nThese clusters are called **Strongly Connected Components (SCCs)**, and finding them is one of the most important graph problems you will encounter. SCCs appear in social network analysis (groups of people who all follow each other), compiler optimization (cycles in function call graphs), and even in solving boolean satisfiability problems. In interviews, SCC questions test whether you can think beyond basic DFS and understand the deeper structure of directed graphs.\n\nKosaraju's algorithm finds all SCCs in a directed graph with two elegant passes of DFS. It is conceptually simpler than the alternative (Tarjan's algorithm) and a great way to build intuition about why the structure of finish times in DFS carries so much information.\n\n---\n\n# What Are Strongly Connected Components?\n\nIn an undirected graph, a connected component is a group of vertices where every vertex can reach every other vertex. Simple enough. But in a directed graph, things get more interesting because edges have direction. Just because you can get from A to B does not mean you can get from B back to A.\n\nA **Strongly Connected Component (SCC)** is a maximal set of vertices such that for every pair of vertices u and v in the set, there is a directed path from u to v AND a directed path from v to u. \"Maximal\" means you cannot add any more vertices to the set and keep this property.\n\nLet us look at an example.\n\n\n```mermaid\nflowchart LR\n A:::cyan --> B:::cyan\n B --> C:::cyan\n C --> A\n C --> D:::orange\n D --> E:::orange\n E --> F:::orange\n F --> D\n E --> G:::teal\n G --> H:::teal\n H --> G\n\n classDef cyan 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\nThis graph has three SCCs:\n\n- **SCC 1 (cyan):** {A, B, C}. A can reach B, B can reach C, C can reach A. Every pair can reach every other pair.\n- **SCC 2 (orange):** {D, E, F}. D reaches E, E reaches F, F reaches D. Fully connected cycle.\n- **SCC 3 (teal):** {G, H}. G reaches H and H reaches G.\n\nNotice that C can reach D (through the edge C to D), but D cannot reach C. So C and D are in different SCCs. The edges between SCCs always go in one direction, which is a property we will exploit later.\n\n---\n\n# What Is Kosaraju's Algorithm?\n\nKosaraju's algorithm finds all SCCs in a directed graph in O(V + E) time using two passes of DFS. The algorithm was independently discovered by S. Rao Kosaraju in 1978 and later published by Micha Sharir in 1981.\n\nThe algorithm has three steps:\n\n1. **First DFS pass:** Run DFS on the original graph. As each vertex finishes (all its descendants have been fully explored), push it onto a stack. This records the \"finish order.\"\n2. **Transpose the graph:** Reverse the direction of every edge in the graph. If there was an edge from u to v, now there is an edge from v to u.\n3. **Second DFS pass:** Pop vertices from the stack one by one. For each unvisited vertex, run DFS on the transposed graph. Each DFS tree you get in this pass is one SCC.\n\nThat is the entire algorithm. Three steps, two DFS passes, one transpose. The beauty of it is that each step is straightforward on its own, and the magic comes from how they work together.\n\n---\n\n# How Kosaraju's Works\n\nLet us walk through each step in detail using a concrete graph.\n\n### The Example Graph\n\nConsider this directed graph with 8 vertices:\n\n\n```mermaid\nflowchart LR\n 0:::cyan --> 1:::cyan\n 1 --> 2:::cyan\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 cyan 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}. Now let us see how Kosaraju's algorithm discovers them.\n\n### Step 1: DFS on the Original Graph (Record Finish Order)\n\nRun DFS starting from any unvisited vertex. When a vertex has no more unvisited neighbors (or all recursive calls from it have returned), push it onto a stack.\n\nSuppose we start DFS from vertex 0:\n\n- Visit 0, go to 1\n- Visit 1, go to 2\n- Visit 2, go to 0 (already visited), go to 3\n- Visit 3, go to 4\n- Visit 4, go to 5\n- Visit 5, go to 3 (already visited), go to 6\n- Visit 6, go to 7\n- Visit 7, go to 6 (already visited), 7 finishes. Push **7**.\n- 6 finishes. Push **6**.\n- 5 finishes. Push **5**.\n- 4 finishes. Push **4**.\n- 3 finishes. Push **3**.\n- 2 finishes. Push **2**.\n- 1 finishes. Push **1**.\n- 0 finishes. Push **0**.\n\nStack (top to bottom): **0, 1, 2, 3, 4, 5, 6, 7**\n\nThe vertex that finishes last ends up on top. This is the key piece of information for step 3.\n\n\n```mermaid\nflowchart LR\n S[\"Stack (top)\"]:::cyan --> N0[\"0\"]:::cyan\n N0 --> N1[\"1\"]:::cyan\n N1 --> N2[\"2\"]:::cyan\n N2 --> N3[\"3\"]:::orange\n N3 --> N4[\"4\"]:::orange\n N4 --> N5[\"5\"]:::orange\n N5 --> N6[\"6\"]:::teal\n N6 --> N7[\"7 (bottom)\"]:::teal\n\n classDef cyan 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\n### Step 2: Transpose the Graph\n\nReverse every edge in the original graph. If the original had an edge from u to v, the transposed graph has an edge from v to u.\n\n\n```mermaid\nflowchart RL\n 0:::cyan --> 2:::cyan\n 1:::cyan --> 0\n 2 --> 1\n 3:::orange --> 2\n 4:::orange --> 3\n 5:::orange --> 4\n 3 --> 5\n 6:::teal --> 5\n 7:::teal --> 6\n 6 --> 7\n\n classDef cyan 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\nNotice something important: the edges within each SCC still form a cycle. If A could reach B and B could reach A in the original, the same is true in the transpose. But the edges between SCCs have flipped direction. In the original, SCC {0,1,2} could reach SCC {3,4,5}. In the transpose, SCC {3,4,5} can reach SCC {0,1,2}. This reversal is crucial.\n\n### Step 3: DFS on the Transposed Graph (In Stack Order)\n\nPop vertices from the stack and run DFS on the transposed graph, skipping already-visited vertices. Each DFS tree is one SCC.\n\n**Pop 0:** DFS from 0 on the transposed graph visits 0 to 2 to 1. All three are in one DFS tree. **SCC found: {0, 1, 2}.**\n\n**Pop 1:** Already visited. Skip.\n\n**Pop 2:** Already visited. Skip.\n\n**Pop 3:** DFS from 3 on the transposed graph visits 3 to 5 to 4. (3 cannot reach 2 because 2 is already visited.) **SCC found: {3, 4, 5}.**\n\n**Pop 4, 5:** Already visited. Skip.\n\n**Pop 6:** DFS from 6 on the transposed graph visits 6 to 7. (6 cannot reach 5 because 5 is already visited.) **SCC found: {6, 7}.**\n\n**Pop 7:** Already visited. Skip.\n\nResult: three SCCs, exactly as expected.\n\n---\n\n# Why It Works\n\nThis is the part most resources skip or hand-wave, but understanding the \"why\" is what makes the algorithm stick.\n\n### Finish Order Encodes SCC Structure\n\nWhen DFS finishes exploring a vertex, it means all vertices reachable from that vertex have already been explored. This means a vertex in an \"upstream\" SCC (one that can reach other SCCs) will finish after vertices in \"downstream\" SCCs.\n\nIn our example, vertices in SCC {0,1,2} finish after vertices in SCC {3,4,5}, which finish after vertices in SCC {6,7}. So the stack has the \"source\" SCCs on top.\n\n### The Transpose Reverses Inter-SCC Edges\n\nWithin an SCC, reversing edges does not change reachability. If u can reach v and v can reach u, the same holds after reversal.\n\nBut between SCCs, the direction flips. In the original graph, SCC-A reaches SCC-B. In the transpose, SCC-B reaches SCC-A.\n\n### Combining the Two\n\nWhen we process the stack in step 3, we start with a vertex from a \"source\" SCC in the original graph. In the transposed graph, this SCC becomes a \"sink\" (no outgoing inter-SCC edges). So DFS from this vertex explores only vertices within its own SCC, because there are no outgoing edges to other SCCs in the transpose.\n\nOnce that SCC is fully marked as visited, we move to the next vertex in the stack. The same logic applies: the DFS can only reach vertices within its own SCC because (a) inter-SCC edges now point inward (not outward) and (b) any SCC that could be reached has already been visited.\n\nThis is why the algorithm works: the finish order plus the transpose together ensure that each DFS in step 3 is perfectly contained within one SCC.\n\n---\n\n# Implementation\n\nHere is the complete implementation of Kosaraju's algorithm.\n\n\n```java\nimport java.util.*;\n\npublic class KosarajuSCC {\n\n // Step 1: DFS on original graph, fill the stack with finish order\n private static void dfs(int node, List> graph, boolean[] visited, Stack stack) {\n visited[node] = true;\n for (int neighbor : graph.get(node)) {\n if (!visited[neighbor]) {\n dfs(neighbor, graph, visited, stack);\n }\n }\n stack.push(node);\n }\n\n // Step 3: DFS on transposed graph to collect one SCC\n private static void dfsTranspose(int node, List> transpose, boolean[] visited, List component) {\n visited[node] = true;\n component.add(node);\n for (int neighbor : transpose.get(node)) {\n if (!visited[neighbor]) {\n dfsTranspose(neighbor, transpose, visited, component);\n }\n }\n }\n\n public static List> findSCCs(int n, List> graph) {\n // Step 1: Fill the stack with finish order\n boolean[] visited = new boolean[n];\n Stack stack = new Stack<>();\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, graph, visited, stack);\n }\n }\n\n // Step 2: Build the transposed graph\n List> transpose = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n transpose.add(new ArrayList<>());\n }\n for (int u = 0; u < n; u++) {\n for (int v : graph.get(u)) {\n transpose.get(v).add(u);\n }\n }\n\n // Step 3: DFS on transposed graph in reverse finish order\n Arrays.fill(visited, false);\n List> sccs = new ArrayList<>();\n while (!stack.isEmpty()) {\n int node = stack.pop();\n if (!visited[node]) {\n List component = new ArrayList<>();\n dfsTranspose(node, transpose, visited, component);\n sccs.add(component);\n }\n }\n\n return sccs;\n }\n\n public static void main(String[] args) {\n int n = 8;\n List> graph = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n graph.add(new ArrayList<>());\n }\n\n // SCC 1: {0, 1, 2}\n graph.get(0).add(1);\n graph.get(1).add(2);\n graph.get(2).add(0);\n\n // Bridge: 2 -> 3\n graph.get(2).add(3);\n\n // SCC 2: {3, 4, 5}\n graph.get(3).add(4);\n graph.get(4).add(5);\n graph.get(5).add(3);\n\n // Bridge: 5 -> 6\n graph.get(5).add(6);\n\n // SCC 3: {6, 7}\n graph.get(6).add(7);\n graph.get(7).add(6);\n\n List> sccs = findSCCs(n, graph);\n\n System.out.println(\"Strongly Connected Components:\");\n for (List scc : sccs) {\n System.out.println(scc);\n }\n }\n}\n```\n\n```python\nfrom collections import defaultdict\n\ndef dfs(node: int, graph: list[list[int]], visited: list[bool], stack: list[int]) -> None:\n \"\"\"Step 1: DFS on original graph, fill the stack with finish order.\"\"\"\n visited[node] = True\n for neighbor in graph[node]:\n if not visited[neighbor]:\n dfs(neighbor, graph, visited, stack)\n stack.append(node)\n\ndef dfs_transpose(node: int, transpose: list[list[int]], visited: list[bool], component: list[int]) -> None:\n \"\"\"Step 3: DFS on transposed graph to collect one SCC.\"\"\"\n visited[node] = True\n component.append(node)\n for neighbor in transpose[node]:\n if not visited[neighbor]:\n dfs_transpose(neighbor, transpose, visited, component)\n\ndef find_sccs(n: int, graph: list[list[int]]) -> list[list[int]]:\n # Step 1: Fill the stack with finish order\n visited = [False] * n\n stack: list[int] = []\n for i in range(n):\n if not visited[i]:\n dfs(i, graph, visited, stack)\n\n # Step 2: Build the transposed graph\n transpose: list[list[int]] = [[] for _ in range(n)]\n for u in range(n):\n for v in graph[u]:\n transpose[v].append(u)\n\n # Step 3: DFS on transposed graph in reverse finish order\n visited = [False] * n\n sccs: list[list[int]] = []\n while stack:\n node = stack.pop()\n if not visited[node]:\n component: list[int] = []\n dfs_transpose(node, transpose, visited, component)\n sccs.append(component)\n\n return sccs\n\nif __name__ == \"__main__\":\n n = 8\n graph: list[list[int]] = [[] for _ in range(n)]\n\n # SCC 1: {0, 1, 2}\n graph[0].append(1)\n graph[1].append(2)\n graph[2].append(0)\n\n # Bridge: 2 -> 3\n graph[2].append(3)\n\n # SCC 2: {3, 4, 5}\n graph[3].append(4)\n graph[4].append(5)\n graph[5].append(3)\n\n # Bridge: 5 -> 6\n graph[5].append(6)\n\n # SCC 3: {6, 7}\n graph[6].append(7)\n graph[7].append(6)\n\n sccs = find_sccs(n, graph)\n\n print(\"Strongly Connected Components:\")\n for scc in sccs:\n print(scc)\n```\n\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\n// Step 1: DFS on original graph, fill the stack with finish order\nvoid dfs(int node, vector>& graph, vector& visited, stack& stk) {\n visited[node] = true;\n for (int neighbor : graph[node]) {\n if (!visited[neighbor]) {\n dfs(neighbor, graph, visited, stk);\n }\n }\n stk.push(node);\n}\n\n// Step 3: DFS on transposed graph to collect one SCC\nvoid dfsTranspose(int node, vector>& transpose, vector& visited, vector& component) {\n visited[node] = true;\n component.push_back(node);\n for (int neighbor : transpose[node]) {\n if (!visited[neighbor]) {\n dfsTranspose(neighbor, transpose, visited, component);\n }\n }\n}\n\nvector> findSCCs(int n, vector>& graph) {\n // Step 1: Fill the stack with finish order\n vector visited(n, false);\n stack stk;\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, graph, visited, stk);\n }\n }\n\n // Step 2: Build the transposed graph\n vector> transpose(n);\n for (int u = 0; u < n; u++) {\n for (int v : graph[u]) {\n transpose[v].push_back(u);\n }\n }\n\n // Step 3: DFS on transposed graph in reverse finish order\n fill(visited.begin(), visited.end(), false);\n vector> sccs;\n while (!stk.empty()) {\n int node = stk.top();\n stk.pop();\n if (!visited[node]) {\n vector component;\n dfsTranspose(node, transpose, visited, component);\n sccs.push_back(component);\n }\n }\n\n return sccs;\n}\n\nint main() {\n int n = 8;\n vector> graph(n);\n\n // SCC 1: {0, 1, 2}\n graph[0].push_back(1);\n graph[1].push_back(2);\n graph[2].push_back(0);\n\n // Bridge: 2 -> 3\n graph[2].push_back(3);\n\n // SCC 2: {3, 4, 5}\n graph[3].push_back(4);\n graph[4].push_back(5);\n graph[5].push_back(3);\n\n // Bridge: 5 -> 6\n graph[5].push_back(6);\n\n // SCC 3: {6, 7}\n graph[6].push_back(7);\n graph[7].push_back(6);\n\n vector> sccs = findSCCs(n, graph);\n\n cout << \"Strongly Connected Components:\" << endl;\n for (auto& scc : sccs) {\n cout << \"[\";\n for (int i = 0; i < scc.size(); i++) {\n cout << scc[i];\n if (i < scc.size() - 1) cout << \", \";\n }\n cout << \"]\" << endl;\n }\n\n return 0;\n}\n```\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\npublic class KosarajuSCC\n{\n // Step 1: DFS on original graph, fill the stack with finish order\n private static void Dfs(int node, List> graph, bool[] visited, Stack stack)\n {\n visited[node] = true;\n foreach (int neighbor in graph[node])\n {\n if (!visited[neighbor])\n {\n Dfs(neighbor, graph, visited, stack);\n }\n }\n stack.Push(node);\n }\n\n // Step 3: DFS on transposed graph to collect one SCC\n private static void DfsTranspose(int node, List> transpose, bool[] visited, List component)\n {\n visited[node] = true;\n component.Add(node);\n foreach (int neighbor in transpose[node])\n {\n if (!visited[neighbor])\n {\n DfsTranspose(neighbor, transpose, visited, component);\n }\n }\n }\n\n public static List> FindSCCs(int n, List> graph)\n {\n // Step 1: Fill the stack with finish order\n bool[] visited = new bool[n];\n Stack stack = new Stack();\n for (int i = 0; i < n; i++)\n {\n if (!visited[i])\n {\n Dfs(i, graph, visited, stack);\n }\n }\n\n // Step 2: Build the transposed graph\n List> transpose = new List>();\n for (int i = 0; i < n; i++)\n {\n transpose.Add(new List());\n }\n for (int u = 0; u < n; u++)\n {\n foreach (int v in graph[u])\n {\n transpose[v].Add(u);\n }\n }\n\n // Step 3: DFS on transposed graph in reverse finish order\n Array.Fill(visited, false);\n List> sccs = new List>();\n while (stack.Count > 0)\n {\n int node = stack.Pop();\n if (!visited[node])\n {\n List component = new List();\n DfsTranspose(node, transpose, visited, component);\n sccs.Add(component);\n }\n }\n\n return sccs;\n }\n\n public static void Main(string[] args)\n {\n int n = 8;\n List> graph = new List>();\n for (int i = 0; i < n; i++)\n {\n graph.Add(new List());\n }\n\n // SCC 1: {0, 1, 2}\n graph[0].Add(1);\n graph[1].Add(2);\n graph[2].Add(0);\n\n // Bridge: 2 -> 3\n graph[2].Add(3);\n\n // SCC 2: {3, 4, 5}\n graph[3].Add(4);\n graph[4].Add(5);\n graph[5].Add(3);\n\n // Bridge: 5 -> 6\n graph[5].Add(6);\n\n // SCC 3: {6, 7}\n graph[6].Add(7);\n graph[7].Add(6);\n\n List> sccs = FindSCCs(n, graph);\n\n Console.WriteLine(\"Strongly Connected Components:\");\n foreach (List scc in sccs)\n {\n Console.WriteLine(\"[\" + string.Join(\", \", scc) + \"]\");\n }\n }\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\n// Step 1: DFS on original graph, fill the stack with finish order\nfunc dfs(node int, graph [][]int, visited []bool, stack *[]int) {\n\tvisited[node] = true\n\tfor _, neighbor := range graph[node] {\n\t\tif !visited[neighbor] {\n\t\t\tdfs(neighbor, graph, visited, stack)\n\t\t}\n\t}\n\t*stack = append(*stack, node)\n}\n\n// Step 3: DFS on transposed graph to collect one SCC\nfunc dfsTranspose(node int, transpose [][]int, visited []bool, component *[]int) {\n\tvisited[node] = true\n\t*component = append(*component, node)\n\tfor _, neighbor := range transpose[node] {\n\t\tif !visited[neighbor] {\n\t\t\tdfsTranspose(neighbor, transpose, visited, component)\n\t\t}\n\t}\n}\n\nfunc FindSCCs(n int, graph [][]int) [][]int {\n\t// Step 1: Fill the stack with finish order\n\tvisited := make([]bool, n)\n\tstack := []int{}\n\tfor i := 0; i < n; i++ {\n\t\tif !visited[i] {\n\t\t\tdfs(i, graph, visited, &stack)\n\t\t}\n\t}\n\n\t// Step 2: Build the transposed graph\n\ttranspose := make([][]int, n)\n\tfor i := 0; i < n; i++ {\n\t\ttranspose[i] = []int{}\n\t}\n\tfor u := 0; u < n; u++ {\n\t\tfor _, v := range graph[u] {\n\t\t\ttranspose[v] = append(transpose[v], u)\n\t\t}\n\t}\n\n\t// Step 3: DFS on transposed graph in reverse finish order\n\tfor i := range visited {\n\t\tvisited[i] = false\n\t}\n\tsccs := [][]int{}\n\tfor len(stack) > 0 {\n\t\tnode := stack[len(stack)-1]\n\t\tstack = stack[:len(stack)-1]\n\t\tif !visited[node] {\n\t\t\tcomponent := []int{}\n\t\t\tdfsTranspose(node, transpose, visited, &component)\n\t\t\tsccs = append(sccs, component)\n\t\t}\n\t}\n\n\treturn sccs\n}\n\nfunc main() {\n\tn := 8\n\tgraph := make([][]int, n)\n\tfor i := 0; i < n; i++ {\n\t\tgraph[i] = []int{}\n\t}\n\n\t// SCC 1: {0, 1, 2}\n\tgraph[0] = append(graph[0], 1)\n\tgraph[1] = append(graph[1], 2)\n\tgraph[2] = append(graph[2], 0)\n\n\t// Bridge: 2 -> 3\n\tgraph[2] = append(graph[2], 3)\n\n\t// SCC 2: {3, 4, 5}\n\tgraph[3] = append(graph[3], 4)\n\tgraph[4] = append(graph[4], 5)\n\tgraph[5] = append(graph[5], 3)\n\n\t// Bridge: 5 -> 6\n\tgraph[5] = append(graph[5], 6)\n\n\t// SCC 3: {6, 7}\n\tgraph[6] = append(graph[6], 7)\n\tgraph[7] = append(graph[7], 6)\n\n\tsccs := FindSCCs(n, graph)\n\n\tfmt.Println(\"Strongly Connected Components:\")\n\tfor _, scc := range sccs {\n\t\tfmt.Println(scc)\n\t}\n}\n```\n\n```javascript\n// Step 1: DFS on original graph, fill the stack with finish order\nfunction dfs(node, graph, visited, stack) {\n visited[node] = true;\n for (const neighbor of graph[node]) {\n if (!visited[neighbor]) {\n dfs(neighbor, graph, visited, stack);\n }\n }\n stack.push(node);\n}\n\n// Step 3: DFS on transposed graph to collect one SCC\nfunction dfsTranspose(node, transpose, visited, component) {\n visited[node] = true;\n component.push(node);\n for (const neighbor of transpose[node]) {\n if (!visited[neighbor]) {\n dfsTranspose(neighbor, transpose, visited, component);\n }\n }\n}\n\nfunction findSCCs(n, graph) {\n // Step 1: Fill the stack with finish order\n const visited = new Array(n).fill(false);\n const stack = [];\n for (let i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, graph, visited, stack);\n }\n }\n\n // Step 2: Build the transposed graph\n const transpose = Array.from({ length: n }, () => []);\n for (let u = 0; u < n; u++) {\n for (const v of graph[u]) {\n transpose[v].push(u);\n }\n }\n\n // Step 3: DFS on transposed graph in reverse finish order\n visited.fill(false);\n const sccs = [];\n while (stack.length > 0) {\n const node = stack.pop();\n if (!visited[node]) {\n const component = [];\n dfsTranspose(node, transpose, visited, component);\n sccs.push(component);\n }\n }\n\n return sccs;\n}\n\n// Main\nconst n = 8;\nconst graph = Array.from({ length: n }, () => []);\n\n// SCC 1: {0, 1, 2}\ngraph[0].push(1);\ngraph[1].push(2);\ngraph[2].push(0);\n\n// Bridge: 2 -> 3\ngraph[2].push(3);\n\n// SCC 2: {3, 4, 5}\ngraph[3].push(4);\ngraph[4].push(5);\ngraph[5].push(3);\n\n// Bridge: 5 -> 6\ngraph[5].push(6);\n\n// SCC 3: {6, 7}\ngraph[6].push(7);\ngraph[7].push(6);\n\nconst sccs = findSCCs(n, graph);\n\nconsole.log(\"Strongly Connected Components:\");\nfor (const scc of sccs) {\n console.log(scc);\n}\n```\n\n```typescript\n// Step 1: DFS on original graph, fill the stack with finish order\nfunction dfs(node: number, graph: number[][], visited: boolean[], stack: number[]): void {\n visited[node] = true;\n for (const neighbor of graph[node]) {\n if (!visited[neighbor]) {\n dfs(neighbor, graph, visited, stack);\n }\n }\n stack.push(node);\n}\n\n// Step 3: DFS on transposed graph to collect one SCC\nfunction dfsTranspose(node: number, transpose: number[][], visited: boolean[], component: number[]): void {\n visited[node] = true;\n component.push(node);\n for (const neighbor of transpose[node]) {\n if (!visited[neighbor]) {\n dfsTranspose(neighbor, transpose, visited, component);\n }\n }\n}\n\nfunction findSCCs(n: number, graph: number[][]): number[][] {\n // Step 1: Fill the stack with finish order\n const visited: boolean[] = new Array(n).fill(false);\n const stack: number[] = [];\n for (let i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, graph, visited, stack);\n }\n }\n\n // Step 2: Build the transposed graph\n const transpose: number[][] = Array.from({ length: n }, () => []);\n for (let u = 0; u < n; u++) {\n for (const v of graph[u]) {\n transpose[v].push(u);\n }\n }\n\n // Step 3: DFS on transposed graph in reverse finish order\n visited.fill(false);\n const sccs: number[][] = [];\n while (stack.length > 0) {\n const node = stack.pop()!;\n if (!visited[node]) {\n const component: number[] = [];\n dfsTranspose(node, transpose, visited, component);\n sccs.push(component);\n }\n }\n\n return sccs;\n}\n\n// Main\nconst n = 8;\nconst graph: number[][] = Array.from({ length: n }, () => []);\n\n// SCC 1: {0, 1, 2}\ngraph[0].push(1);\ngraph[1].push(2);\ngraph[2].push(0);\n\n// Bridge: 2 -> 3\ngraph[2].push(3);\n\n// SCC 2: {3, 4, 5}\ngraph[3].push(4);\ngraph[4].push(5);\ngraph[5].push(3);\n\n// Bridge: 5 -> 6\ngraph[5].push(6);\n\n// SCC 3: {6, 7}\ngraph[6].push(7);\ngraph[7].push(6);\n\nconst sccs = findSCCs(n, graph);\n\nconsole.log(\"Strongly Connected Components:\");\nfor (const scc of sccs) {\n console.log(scc);\n}\n```\n\n\n**Output:**\n\n\n```shell\nStrongly Connected Components:\n[0, 2, 1]\n[3, 5, 4]\n[6, 7]\n```\n\n\nThe time complexity is **O(V + E)**. We do two DFS passes, each taking O(V + E), and building the transpose takes O(V + E). The space complexity is **O(V + E)** for the transposed graph, the visited array, and the stack.\n\n---\n\n# Step-by-Step Walkthrough\n\nLet us trace through a slightly different graph to solidify the understanding. Consider this graph with 9 vertices and 4 SCCs:\n\n\n```mermaid\nflowchart LR\n 0:::cyan --> 1:::cyan\n 1 --> 2:::cyan\n 2 --> 0\n\n 1 --> 3:::orange\n 3 --> 4:::orange\n 4 --> 3\n\n 2 --> 5:::teal\n 5 --> 6:::teal\n 6 --> 5\n\n 4 --> 7:::red\n 6 --> 7\n 7 --> 8:::red\n 8 --> 7\n\n classDef cyan 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 red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nSCCs: {0, 1, 2}, {3, 4}, {5, 6}, {7, 8}.\n\n### Pass 1: DFS on Original Graph\n\nStarting from vertex 0:\n\n\n```shell\nDFS(0):\n DFS(1):\n DFS(2):\n -> 0 (visited)\n DFS(5):\n DFS(6):\n -> 5 (visited)\n DFS(7):\n DFS(8):\n -> 7 (visited)\n 8 finishes. Push 8.\n 7 finishes. Push 7.\n 6 finishes. Push 6.\n 5 finishes. Push 5.\n 2 finishes. Push 2.\n DFS(3):\n DFS(4):\n -> 3 (visited)\n -> 7 (visited)\n 4 finishes. Push 4.\n 3 finishes. Push 3.\n 1 finishes. Push 1.\n 0 finishes. Push 0.\n```\n\n\nStack (top to bottom): **0, 1, 3, 4, 2, 5, 6, 7, 8**\n\n### Pass 2: Transpose and DFS\n\nThe transposed graph reverses every edge. Now we pop from the stack:\n\n\n| Pop | Visited? | DFS on Transpose | SCC Found |\n|-----|----------|-------------------|-----------|\n| 0 | No | 0 to 2 to 1 | {0, 2, 1} |\n| 1 | Yes | Skip | - |\n| 3 | No | 3 to 4 | {3, 4} |\n| 4 | Yes | Skip | - |\n| 2 | Yes | Skip | - |\n| 5 | No | 5 to 6 | {5, 6} |\n| 6 | Yes | Skip | - |\n| 7 | No | 7 to 8 | {7, 8} |\n| 8 | Yes | Skip | - |\n\n\n**Result:** 4 SCCs: {0, 2, 1}, {3, 4}, {5, 6}, {7, 8}.\n\nNotice how the stack order prevented any \"leaking\" between SCCs. When we processed vertex 0, DFS on the transpose could not reach vertices 3 or 5 because the inter-SCC edges point away from {0,1,2} in the transpose. When we processed vertex 3, vertices 0, 1, 2 were already visited, so even though the transpose has an edge from 3 to 1, the DFS stops there.\n\n---\n\n# Kosaraju's vs Tarjan's\n\nBoth Kosaraju's and Tarjan's algorithms find all SCCs in O(V + E) time, but they take different approaches.\n\n\n| Aspect | Kosaraju's | Tarjan's |\n|--------|-----------|----------|\n| **DFS passes** | Two (original + transposed graph) | One |\n| **Extra space** | Transposed graph (O(V + E)) | Low-link values and stack (O(V)) |\n| **Conceptual simplicity** | Easier to understand | Harder (requires understanding low-link values) |\n| **Implementation complexity** | Moderate (two DFS + transpose) | Moderate (one DFS but more bookkeeping) |\n| **Time complexity** | O(V + E) | O(V + E) |\n| **Space complexity** | O(V + E) for the transpose | O(V) additional |\n| **Parallelization** | The two passes can partially parallelize | Harder to parallelize |\n| **Practical use** | Great for teaching, used in practice | Preferred when memory is tight |\n\n\n**When to use which?** In an interview, use whichever you are more comfortable implementing correctly under pressure. Both are accepted. If the interviewer specifically asks for a single-pass algorithm, go with Tarjan's. If they ask for something easy to explain, Kosaraju's is the better choice.\n\n---\n\n## Example Problem: Finding the Number of SCCs\n\n**Problem:** Given a directed graph with `n` vertices and a list of directed edges, find the number of strongly connected components.\n\nThis is the direct application of Kosaraju's algorithm. Let us write a clean solution.\n\n\n```java\nimport java.util.*;\n\npublic class CountSCCs {\n\n public static int countSCCs(int n, int[][] edges) {\n // Build adjacency list\n List> graph = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n graph.add(new ArrayList<>());\n }\n for (int[] edge : edges) {\n graph.get(edge[0]).add(edge[1]);\n }\n\n // Step 1: Fill stack with finish order\n boolean[] visited = new boolean[n];\n Stack stack = new Stack<>();\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n fillOrder(i, graph, visited, stack);\n }\n }\n\n // Step 2: Build transposed graph\n List> transpose = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n transpose.add(new ArrayList<>());\n }\n for (int[] edge : edges) {\n transpose.get(edge[1]).add(edge[0]);\n }\n\n // Step 3: Count SCCs\n Arrays.fill(visited, false);\n int count = 0;\n while (!stack.isEmpty()) {\n int node = stack.pop();\n if (!visited[node]) {\n markVisited(node, transpose, visited);\n count++;\n }\n }\n\n return count;\n }\n\n private static void fillOrder(int node, List> graph, boolean[] visited, Stack stack) {\n visited[node] = true;\n for (int neighbor : graph.get(node)) {\n if (!visited[neighbor]) {\n fillOrder(neighbor, graph, visited, stack);\n }\n }\n stack.push(node);\n }\n\n private static void markVisited(int node, List> transpose, boolean[] visited) {\n visited[node] = true;\n for (int neighbor : transpose.get(node)) {\n if (!visited[neighbor]) {\n markVisited(neighbor, transpose, visited);\n }\n }\n }\n\n public static void main(String[] args) {\n int n = 5;\n int[][] edges = {\n {0, 1}, {1, 2}, {2, 0}, // SCC: {0, 1, 2}\n {1, 3}, // Bridge\n {3, 4}, {4, 3} // SCC: {3, 4}\n };\n\n System.out.println(\"Number of SCCs: \" + countSCCs(n, edges));\n // Output: Number of SCCs: 2\n }\n}\n```\n\n```python\ndef count_sccs(n: int, edges: list[list[int]]) -> int:\n # Build adjacency list\n graph: list[list[int]] = [[] for _ in range(n)]\n for u, v in edges:\n graph[u].append(v)\n\n # Step 1: Fill stack with finish order\n visited = [False] * n\n stack: list[int] = []\n\n def fill_order(node: int) -> None:\n visited[node] = True\n for neighbor in graph[node]:\n if not visited[neighbor]:\n fill_order(neighbor)\n stack.append(node)\n\n for i in range(n):\n if not visited[i]:\n fill_order(i)\n\n # Step 2: Build transposed graph\n transpose: list[list[int]] = [[] for _ in range(n)]\n for u, v in edges:\n transpose[v].append(u)\n\n # Step 3: Count SCCs\n visited = [False] * n\n\n def mark_visited(node: int) -> None:\n visited[node] = True\n for neighbor in transpose[node]:\n if not visited[neighbor]:\n mark_visited(neighbor)\n\n count = 0\n while stack:\n node = stack.pop()\n if not visited[node]:\n mark_visited(node)\n count += 1\n\n return count\n\nif __name__ == \"__main__\":\n n = 5\n edges = [\n [0, 1], [1, 2], [2, 0], # SCC: {0, 1, 2}\n [1, 3], # Bridge\n [3, 4], [4, 3] # SCC: {3, 4}\n ]\n\n print(f\"Number of SCCs: {count_sccs(n, edges)}\")\n # Output: Number of SCCs: 2\n```\n\n```cpp\n#include \n#include \n#include \n#include \nusing namespace std;\n\nclass CountSCCs {\npublic:\n static int countSCCs(int n, vector>& edges) {\n // Build adjacency list\n vector> graph(n);\n for (auto& edge : edges) {\n graph[edge[0]].push_back(edge[1]);\n }\n\n // Step 1: Fill stack with finish order\n vector visited(n, false);\n stack stk;\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n fillOrder(i, graph, visited, stk);\n }\n }\n\n // Step 2: Build transposed graph\n vector> transpose(n);\n for (auto& edge : edges) {\n transpose[edge[1]].push_back(edge[0]);\n }\n\n // Step 3: Count SCCs\n fill(visited.begin(), visited.end(), false);\n int count = 0;\n while (!stk.empty()) {\n int node = stk.top();\n stk.pop();\n if (!visited[node]) {\n markVisited(node, transpose, visited);\n count++;\n }\n }\n\n return count;\n }\n\nprivate:\n static void fillOrder(int node, vector>& graph, vector& visited, stack& stk) {\n visited[node] = true;\n for (int neighbor : graph[node]) {\n if (!visited[neighbor]) {\n fillOrder(neighbor, graph, visited, stk);\n }\n }\n stk.push(node);\n }\n\n static void markVisited(int node, vector>& transpose, vector& visited) {\n visited[node] = true;\n for (int neighbor : transpose[node]) {\n if (!visited[neighbor]) {\n markVisited(neighbor, transpose, visited);\n }\n }\n }\n};\n\nint main() {\n int n = 5;\n vector> edges = {\n {0, 1}, {1, 2}, {2, 0}, // SCC: {0, 1, 2}\n {1, 3}, // Bridge\n {3, 4}, {4, 3} // SCC: {3, 4}\n };\n\n cout << \"Number of SCCs: \" << CountSCCs::countSCCs(n, edges) << endl;\n // Output: Number of SCCs: 2\n\n return 0;\n}\n```\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\npublic class CountSCCs\n{\n public static int Count(int n, int[][] edges)\n {\n // Build adjacency list\n List> graph = new List>();\n for (int i = 0; i < n; i++)\n graph.Add(new List());\n foreach (int[] edge in edges)\n graph[edge[0]].Add(edge[1]);\n\n // Step 1: Fill stack with finish order\n bool[] visited = new bool[n];\n Stack stack = new Stack();\n for (int i = 0; i < n; i++)\n {\n if (!visited[i])\n FillOrder(i, graph, visited, stack);\n }\n\n // Step 2: Build transposed graph\n List> transpose = new List>();\n for (int i = 0; i < n; i++)\n transpose.Add(new List());\n foreach (int[] edge in edges)\n transpose[edge[1]].Add(edge[0]);\n\n // Step 3: Count SCCs\n Array.Fill(visited, false);\n int count = 0;\n while (stack.Count > 0)\n {\n int node = stack.Pop();\n if (!visited[node])\n {\n MarkVisited(node, transpose, visited);\n count++;\n }\n }\n\n return count;\n }\n\n private static void FillOrder(int node, List> graph, bool[] visited, Stack stack)\n {\n visited[node] = true;\n foreach (int neighbor in graph[node])\n {\n if (!visited[neighbor])\n FillOrder(neighbor, graph, visited, stack);\n }\n stack.Push(node);\n }\n\n private static void MarkVisited(int node, List> transpose, bool[] visited)\n {\n visited[node] = true;\n foreach (int neighbor in transpose[node])\n {\n if (!visited[neighbor])\n MarkVisited(neighbor, transpose, visited);\n }\n }\n\n public static void Main(string[] args)\n {\n int n = 5;\n int[][] edges = new int[][] {\n new[] {0, 1}, new[] {1, 2}, new[] {2, 0}, // SCC: {0, 1, 2}\n new[] {1, 3}, // Bridge\n new[] {3, 4}, new[] {4, 3} // SCC: {3, 4}\n };\n\n Console.WriteLine($\"Number of SCCs: {Count(n, edges)}\");\n // Output: Number of SCCs: 2\n }\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\nfunc countSCCs(n int, edges [][]int) int {\n\t// Build adjacency list\n\tgraph := make([][]int, n)\n\tfor i := 0; i < n; i++ {\n\t\tgraph[i] = []int{}\n\t}\n\tfor _, edge := range edges {\n\t\tgraph[edge[0]] = append(graph[edge[0]], edge[1])\n\t}\n\n\t// Step 1: Fill stack with finish order\n\tvisited := make([]bool, n)\n\tstack := []int{}\n\n\tvar fillOrder func(node int)\n\tfillOrder = func(node int) {\n\t\tvisited[node] = true\n\t\tfor _, neighbor := range graph[node] {\n\t\t\tif !visited[neighbor] {\n\t\t\t\tfillOrder(neighbor)\n\t\t\t}\n\t\t}\n\t\tstack = append(stack, node)\n\t}\n\n\tfor i := 0; i < n; i++ {\n\t\tif !visited[i] {\n\t\t\tfillOrder(i)\n\t\t}\n\t}\n\n\t// Step 2: Build transposed graph\n\ttranspose := make([][]int, n)\n\tfor i := 0; i < n; i++ {\n\t\ttranspose[i] = []int{}\n\t}\n\tfor _, edge := range edges {\n\t\ttranspose[edge[1]] = append(transpose[edge[1]], edge[0])\n\t}\n\n\t// Step 3: Count SCCs\n\tfor i := range visited {\n\t\tvisited[i] = false\n\t}\n\n\tvar markVisited func(node int)\n\tmarkVisited = func(node int) {\n\t\tvisited[node] = true\n\t\tfor _, neighbor := range transpose[node] {\n\t\t\tif !visited[neighbor] {\n\t\t\t\tmarkVisited(neighbor)\n\t\t\t}\n\t\t}\n\t}\n\n\tcount := 0\n\tfor len(stack) > 0 {\n\t\tnode := stack[len(stack)-1]\n\t\tstack = stack[:len(stack)-1]\n\t\tif !visited[node] {\n\t\t\tmarkVisited(node)\n\t\t\tcount++\n\t\t}\n\t}\n\n\treturn count\n}\n\nfunc main() {\n\tn := 5\n\tedges := [][]int{\n\t\t{0, 1}, {1, 2}, {2, 0}, // SCC: {0, 1, 2}\n\t\t{1, 3}, // Bridge\n\t\t{3, 4}, {4, 3}, // SCC: {3, 4}\n\t}\n\n\tfmt.Printf(\"Number of SCCs: %d\\n\", countSCCs(n, edges))\n\t// Output: Number of SCCs: 2\n}\n```\n\n```javascript\nfunction countSCCs(n, edges) {\n // Build adjacency list\n const graph = Array.from({ length: n }, () => []);\n for (const [u, v] of edges) {\n graph[u].push(v);\n }\n\n // Step 1: Fill stack with finish order\n const visited = new Array(n).fill(false);\n const stack = [];\n\n function fillOrder(node) {\n visited[node] = true;\n for (const neighbor of graph[node]) {\n if (!visited[neighbor]) {\n fillOrder(neighbor);\n }\n }\n stack.push(node);\n }\n\n for (let i = 0; i < n; i++) {\n if (!visited[i]) {\n fillOrder(i);\n }\n }\n\n // Step 2: Build transposed graph\n const transpose = Array.from({ length: n }, () => []);\n for (const [u, v] of edges) {\n transpose[v].push(u);\n }\n\n // Step 3: Count SCCs\n visited.fill(false);\n\n function markVisited(node) {\n visited[node] = true;\n for (const neighbor of transpose[node]) {\n if (!visited[neighbor]) {\n markVisited(neighbor);\n }\n }\n }\n\n let count = 0;\n while (stack.length > 0) {\n const node = stack.pop();\n if (!visited[node]) {\n markVisited(node);\n count++;\n }\n }\n\n return count;\n}\n\n// Main\nconst n = 5;\nconst edges = [\n [0, 1], [1, 2], [2, 0], // SCC: {0, 1, 2}\n [1, 3], // Bridge\n [3, 4], [4, 3] // SCC: {3, 4}\n];\n\nconsole.log(`Number of SCCs: ${countSCCs(n, edges)}`);\n// Output: Number of SCCs: 2\n```\n\n```typescript\nfunction countSCCs(n: number, edges: number[][]): number {\n // Build adjacency list\n const graph: number[][] = Array.from({ length: n }, () => []);\n for (const [u, v] of edges) {\n graph[u].push(v);\n }\n\n // Step 1: Fill stack with finish order\n const visited: boolean[] = new Array(n).fill(false);\n const stack: number[] = [];\n\n function fillOrder(node: number): void {\n visited[node] = true;\n for (const neighbor of graph[node]) {\n if (!visited[neighbor]) {\n fillOrder(neighbor);\n }\n }\n stack.push(node);\n }\n\n for (let i = 0; i < n; i++) {\n if (!visited[i]) {\n fillOrder(i);\n }\n }\n\n // Step 2: Build transposed graph\n const transpose: number[][] = Array.from({ length: n }, () => []);\n for (const [u, v] of edges) {\n transpose[v].push(u);\n }\n\n // Step 3: Count SCCs\n visited.fill(false);\n\n function markVisited(node: number): void {\n visited[node] = true;\n for (const neighbor of transpose[node]) {\n if (!visited[neighbor]) {\n markVisited(neighbor);\n }\n }\n }\n\n let count = 0;\n while (stack.length > 0) {\n const node = stack.pop()!;\n if (!visited[node]) {\n markVisited(node);\n count++;\n }\n }\n\n return count;\n}\n\n// Main\nconst n = 5;\nconst edges: number[][] = [\n [0, 1], [1, 2], [2, 0], // SCC: {0, 1, 2}\n [1, 3], // Bridge\n [3, 4], [4, 3] // SCC: {3, 4}\n];\n\nconsole.log(`Number of SCCs: ${countSCCs(n, edges)}`);\n// Output: Number of SCCs: 2\n```\n\n\n### Variation: Check if the Graph Is Strongly Connected\n\nA common interview question is: \"Is the entire graph one single SCC?\" This is equivalent to asking whether the number of SCCs is exactly 1.\n\n\n```java\npublic static boolean isStronglyConnected(int n, int[][] edges) {\n return countSCCs(n, edges) == 1;\n}\n```\n\n```python\ndef is_strongly_connected(n: int, edges: list[list[int]]) -> bool:\n return count_sccs(n, edges) == 1\n```\n\n```cpp\nbool isStronglyConnected(int n, vector>& edges) {\n return CountSCCs::countSCCs(n, edges) == 1;\n}\n```\n\n```csharp\npublic static bool IsStronglyConnected(int n, int[][] edges)\n{\n return Count(n, edges) == 1;\n}\n```\n\n```go\nfunc isStronglyConnected(n int, edges [][]int) bool {\n\treturn countSCCs(n, edges) == 1\n}\n```\n\n```javascript\nfunction isStronglyConnected(n, edges) {\n return countSCCs(n, edges) === 1;\n}\n```\n\n```typescript\nfunction isStronglyConnected(n: number, edges: number[][]): boolean {\n return countSCCs(n, edges) === 1;\n}\n```\n\n\nThis runs in O(V + E) and is much more elegant than the naive approach of running DFS from every vertex (which would be O(V * (V + E))).\n\n---\n\n# Applications of SCCs\n\nSCCs are not just a theoretical curiosity. They show up in several important real-world and interview-relevant problems.\n\n### 1. Condensation Graph (DAG of SCCs)\n\nOnce you find all SCCs, you can collapse each SCC into a single vertex. The resulting graph is guaranteed to be a DAG. This condensation is useful for:\n\n- **Reachability queries:** Instead of checking reachability on the original graph, check on the much smaller DAG.\n- **Shortest path in terms of components:** How many SCC boundaries do you need to cross?\n- **Topological ordering of components:** Process SCCs in dependency order.\n\n\n```mermaid\nflowchart LR\n subgraph Original\n A[\"SCC {0,1,2}\"]:::cyan --> B[\"SCC {3,4,5}\"]:::orange\n B --> C[\"SCC {6,7}\"]:::teal\n end\n\n classDef cyan 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\n### 2. 2-SAT (Boolean Satisfiability)\n\nThe 2-SAT problem asks: given a boolean formula where each clause has exactly two literals, is there a satisfying assignment? This can be modeled as an implication graph, and the formula is satisfiable if and only if no variable and its negation are in the same SCC. Kosaraju's algorithm gives you an O(V + E) solution to 2-SAT.\n\n### 3. Social Network Analysis\n\nIn a follow/friend graph, SCCs represent communities where every member can reach every other member through a chain of follows. Finding these communities helps with recommendation systems and influence analysis.\n\n### 4. Compiler Optimization\n\nIn a function call graph, SCCs represent groups of mutually recursive functions. The compiler can optimize these groups differently from non-recursive functions, for example by applying special inlining or tail-call strategies.\n\n---\n\n## Common Mistakes\n\nThese are the pitfalls that trip people up when implementing Kosaraju's algorithm, especially under interview pressure.\n\n### 1. Wrong Finish Order\n\nThe most common mistake is using the discovery order (when you first visit a vertex) instead of the finish order (when all descendants are fully explored). The finish order must record when a vertex has no more unvisited neighbors to explore. Using discovery order will produce incorrect results.\n\n \n\n\n```java\n// WRONG: Recording at discovery time\nprivate static void dfsWrong(int node, List> graph, boolean[] visited, Stack stack) {\n visited[node] = true;\n stack.push(node); // Wrong! This is discovery order, not finish order.\n for (int neighbor : graph.get(node)) {\n if (!visited[neighbor]) {\n dfsWrong(neighbor, graph, visited, stack);\n }\n }\n}\n\n// CORRECT: Recording at finish time\nprivate static void dfsCorrect(int node, List> graph, boolean[] visited, Stack stack) {\n visited[node] = true;\n for (int neighbor : graph.get(node)) {\n if (!visited[neighbor]) {\n dfsCorrect(neighbor, graph, visited, stack);\n }\n }\n stack.push(node); // Correct! Push after all neighbors are explored.\n}\n```\n\n\n \n\n\n```python\n# WRONG: Recording at discovery time\ndef dfs_wrong(node: int, graph: list[list[int]], visited: list[bool], stack: list[int]) -> None:\n visited[node] = True\n stack.append(node) # Wrong! This is discovery order, not finish order.\n for neighbor in graph[node]:\n if not visited[neighbor]:\n dfs_wrong(neighbor, graph, visited, stack)\n\n# CORRECT: Recording at finish time\ndef dfs_correct(node: int, graph: list[list[int]], visited: list[bool], stack: list[int]) -> None:\n visited[node] = True\n for neighbor in graph[node]:\n if not visited[neighbor]:\n dfs_correct(neighbor, graph, visited, stack)\n stack.append(node) # Correct! Append after all neighbors are explored.\n```\n\n\n \n\n\n```cpp\n// WRONG: Recording at discovery time\nvoid dfsWrong(int node, vector>& graph, vector& visited, stack& stk) {\n visited[node] = true;\n stk.push(node); // Wrong! This is discovery order, not finish order.\n for (int neighbor : graph[node]) {\n if (!visited[neighbor]) {\n dfsWrong(neighbor, graph, visited, stk);\n }\n }\n}\n\n// CORRECT: Recording at finish time\nvoid dfsCorrect(int node, vector>& graph, vector& visited, stack& stk) {\n visited[node] = true;\n for (int neighbor : graph[node]) {\n if (!visited[neighbor]) {\n dfsCorrect(neighbor, graph, visited, stk);\n }\n }\n stk.push(node); // Correct! Push after all neighbors are explored.\n}\n```\n\n\n \n\n\n```csharp\n// WRONG: Recording at discovery time\nprivate static void DfsWrong(int node, List> graph, bool[] visited, Stack stack)\n{\n visited[node] = true;\n stack.Push(node); // Wrong! This is discovery order, not finish order.\n foreach (int neighbor in graph[node])\n {\n if (!visited[neighbor])\n DfsWrong(neighbor, graph, visited, stack);\n }\n}\n\n// CORRECT: Recording at finish time\nprivate static void DfsCorrect(int node, List> graph, bool[] visited, Stack stack)\n{\n visited[node] = true;\n foreach (int neighbor in graph[node])\n {\n if (!visited[neighbor])\n DfsCorrect(neighbor, graph, visited, stack);\n }\n stack.Push(node); // Correct! Push after all neighbors are explored.\n}\n```\n\n\n \n\n\n```go\n// WRONG: Recording at discovery time\nfunc dfsWrong(node int, graph [][]int, visited []bool, stack *[]int) {\n\tvisited[node] = true\n\t*stack = append(*stack, node) // Wrong! This is discovery order, not finish order.\n\tfor _, neighbor := range graph[node] {\n\t\tif !visited[neighbor] {\n\t\t\tdfsWrong(neighbor, graph, visited, stack)\n\t\t}\n\t}\n}\n\n// CORRECT: Recording at finish time\nfunc dfsCorrect(node int, graph [][]int, visited []bool, stack *[]int) {\n\tvisited[node] = true\n\tfor _, neighbor := range graph[node] {\n\t\tif !visited[neighbor] {\n\t\t\tdfsCorrect(neighbor, graph, visited, stack)\n\t\t}\n\t}\n\t*stack = append(*stack, node) // Correct! Push after all neighbors are explored.\n}\n```\n\n\n \n\n\n```javascript\n// WRONG: Recording at discovery time\nfunction dfsWrong(node, graph, visited, stack) {\n visited[node] = true;\n stack.push(node); // Wrong! This is discovery order, not finish order.\n for (const neighbor of graph[node]) {\n if (!visited[neighbor]) {\n dfsWrong(neighbor, graph, visited, stack);\n }\n }\n}\n\n// CORRECT: Recording at finish time\nfunction dfsCorrect(node, graph, visited, stack) {\n visited[node] = true;\n for (const neighbor of graph[node]) {\n if (!visited[neighbor]) {\n dfsCorrect(neighbor, graph, visited, stack);\n }\n }\n stack.push(node); // Correct! Push after all neighbors are explored.\n}\n```\n\n\n \n\n\n```typescript\n// WRONG: Recording at discovery time\nfunction dfsWrong(node: number, graph: number[][], visited: boolean[], stack: number[]): void {\n visited[node] = true;\n stack.push(node); // Wrong! This is discovery order, not finish order.\n for (const neighbor of graph[node]) {\n if (!visited[neighbor]) {\n dfsWrong(neighbor, graph, visited, stack);\n }\n }\n}\n\n// CORRECT: Recording at finish time\nfunction dfsCorrect(node: number, graph: number[][], visited: boolean[], stack: number[]): void {\n visited[node] = true;\n for (const neighbor of graph[node]) {\n if (!visited[neighbor]) {\n dfsCorrect(neighbor, graph, visited, stack);\n }\n }\n stack.push(node); // Correct! Push after all neighbors are explored.\n}\n```\n\n\n \n\n### 2. Forgetting to Reset the Visited Array\n\nBetween the first and second DFS passes, you must reset the visited array. The second pass needs a clean slate. Forgetting this means no vertex will be visited in the second pass, and you will find zero SCCs.\n\n \n\n\n```java\n// Don't forget this line between the two passes!\nArrays.fill(visited, false);\n```\n\n\n \n\n\n```python\n# Don't forget this line between the two passes!\nvisited = [False] * n\n```\n\n\n \n\n\n```cpp\n// Don't forget this line between the two passes!\nfill(visited.begin(), visited.end(), false);\n```\n\n\n \n\n\n```csharp\n// Don't forget this line between the two passes!\nArray.Fill(visited, false);\n```\n\n\n \n\n\n```go\n// Don't forget this line between the two passes!\nfor i := range visited {\n visited[i] = false\n}\n```\n\n\n \n\n\n```javascript\n// Don't forget this line between the two passes!\nvisited.fill(false);\n```\n\n\n \n\n\n```typescript\n// Don't forget this line between the two passes!\nvisited.fill(false);\n```\n\n\n \n\n### 3. Incorrect Transpose\n\nWhen building the transposed graph, every edge must be reversed. A common bug is adding the edge in the same direction or reversing only some edges.\n\n \n\n\n```java\n// WRONG\nfor (int[] edge : edges) {\n transpose.get(edge[0]).add(edge[1]); // Same direction, not reversed!\n}\n\n// CORRECT\nfor (int[] edge : edges) {\n transpose.get(edge[1]).add(edge[0]); // Reversed direction\n}\n```\n\n\n \n\n\n```python\n# WRONG\nfor u, v in edges:\n transpose[u].append(v) # Same direction, not reversed!\n\n# CORRECT\nfor u, v in edges:\n transpose[v].append(u) # Reversed direction\n```\n\n\n \n\n\n```cpp\n// WRONG\nfor (auto& edge : edges) {\n transpose[edge[0]].push_back(edge[1]); // Same direction, not reversed!\n}\n\n// CORRECT\nfor (auto& edge : edges) {\n transpose[edge[1]].push_back(edge[0]); // Reversed direction\n}\n```\n\n\n \n\n\n```csharp\n// WRONG\nforeach (int[] edge in edges)\n transpose[edge[0]].Add(edge[1]); // Same direction, not reversed!\n\n// CORRECT\nforeach (int[] edge in edges)\n transpose[edge[1]].Add(edge[0]); // Reversed direction\n```\n\n\n \n\n\n```go\n// WRONG\nfor _, edge := range edges {\n transpose[edge[0]] = append(transpose[edge[0]], edge[1]) // Same direction, not reversed!\n}\n\n// CORRECT\nfor _, edge := range edges {\n transpose[edge[1]] = append(transpose[edge[1]], edge[0]) // Reversed direction\n}\n```\n\n\n \n\n\n```javascript\n// WRONG\nfor (const [u, v] of edges) {\n transpose[u].push(v); // Same direction, not reversed!\n}\n\n// CORRECT\nfor (const [u, v] of edges) {\n transpose[v].push(u); // Reversed direction\n}\n```\n\n\n \n\n\n```typescript\n// WRONG\nfor (const [u, v] of edges) {\n transpose[u].push(v); // Same direction, not reversed!\n}\n\n// CORRECT\nfor (const [u, v] of edges) {\n transpose[v].push(u); // Reversed direction\n}\n```\n\n\n \n\n### 4. Not Handling Disconnected Graphs\n\nIf the graph is disconnected (not all vertices are reachable from a single source), the first DFS pass must start from every unvisited vertex, not just vertex 0. Missing this means some vertices never get pushed onto the stack.\n\n \n\n\n```java\n// Must iterate over all vertices, not just start from 0\nfor (int i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, graph, visited, stack);\n }\n}\n```\n\n\n \n\n\n```python\n# Must iterate over all vertices, not just start from 0\nfor i in range(n):\n if not visited[i]:\n dfs(i, graph, visited, stack)\n```\n\n\n \n\n\n```cpp\n// Must iterate over all vertices, not just start from 0\nfor (int i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, graph, visited, stk);\n }\n}\n```\n\n\n \n\n\n```csharp\n// Must iterate over all vertices, not just start from 0\nfor (int i = 0; i < n; i++)\n{\n if (!visited[i])\n Dfs(i, graph, visited, stack);\n}\n```\n\n\n \n\n\n```go\n// Must iterate over all vertices, not just start from 0\nfor i := 0; i < n; i++ {\n if !visited[i] {\n dfs(i, graph, visited, &stack)\n }\n}\n```\n\n\n \n\n\n```javascript\n// Must iterate over all vertices, not just start from 0\nfor (let i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, graph, visited, stack);\n }\n}\n```\n\n\n \n\n\n```typescript\n// Must iterate over all vertices, not just start from 0\nfor (let i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, graph, visited, stack);\n }\n}\n```\n\n\n \n\n### 5. Stack Overflow on Large Graphs\n\nRecursive DFS can cause a stack overflow on graphs with thousands of vertices. In production code or competitive programming, convert to an iterative approach using an explicit stack. In an interview, mention this limitation and offer to write the iterative version if asked.\n\n---\n\n## Interview Questions\n\n**Q1: What is a Strongly Connected Component? How is it different from a connected component?**\n\nA connected component applies to undirected graphs: it is a maximal set of vertices where every pair has a path between them. An SCC applies to directed graphs: it is a maximal set of vertices where every pair has a directed path in both directions. In an undirected graph, if A can reach B, then B can always reach A, so connected components and SCCs are equivalent. In a directed graph, reachability is not symmetric, so the distinction matters.\n\n**Q2: Why does Kosaraju's algorithm need two DFS passes? Can it be done in one pass?**\n\nThe first pass computes a finish ordering that encodes which SCCs can reach which. The second pass, on the transposed graph, uses this ordering to process SCCs one at a time without leaking into adjacent components. You can do it in one pass using Tarjan's algorithm, which maintains a stack and low-link values to detect SCCs during a single DFS. The tradeoff is that Tarjan's is conceptually harder to understand.\n\n**Q3: What happens if you skip the transpose step and just run the second DFS on the original graph?**\n\nWithout transposing, the second DFS would follow edges out of the current SCC into other SCCs, lumping multiple SCCs together. The transpose ensures that inter-SCC edges point inward (toward the current SCC) rather than outward, so DFS stays contained within the correct SCC.\n\n**Q4: How would you find the number of vertices in the largest SCC?**\n\nRun Kosaraju's algorithm to get all SCCs, then iterate through the list and track the maximum size. The time complexity remains O(V + E) since finding SCCs dominates the cost.\n\n \n\n\n```java\nList> sccs = findSCCs(n, graph);\nint maxSize = 0;\nfor (List scc : sccs) {\n maxSize = Math.max(maxSize, scc.size());\n}\n```\n\n\n \n\n\n```python\nsccs = find_sccs(n, graph)\nmax_size = max(len(scc) for scc in sccs)\n```\n\n\n \n\n\n```cpp\nvector> sccs = findSCCs(n, graph);\nint maxSize = 0;\nfor (auto& scc : sccs) {\n maxSize = max(maxSize, (int)scc.size());\n}\n```\n\n\n \n\n\n```csharp\nList> sccs = FindSCCs(n, graph);\nint maxSize = 0;\nforeach (List scc in sccs)\n{\n maxSize = Math.Max(maxSize, scc.Count);\n}\n```\n\n\n \n\n\n```go\nsccs := FindSCCs(n, graph)\nmaxSize := 0\nfor _, scc := range sccs {\n if len(scc) > maxSize {\n maxSize = len(scc)\n }\n}\n```\n\n\n \n\n\n```javascript\nconst sccs = findSCCs(n, graph);\nlet maxSize = 0;\nfor (const scc of sccs) {\n maxSize = Math.max(maxSize, scc.length);\n}\n```\n\n\n \n\n\n```typescript\nconst sccs: number[][] = findSCCs(n, graph);\nlet maxSize = 0;\nfor (const scc of sccs) {\n maxSize = Math.max(maxSize, scc.length);\n}\n```\n\n\n \n\n**Q5: Given a directed graph, what is the minimum number of edges you need to add to make the entire graph strongly connected?**\n\nFirst, find all SCCs and build the condensation DAG. Count the number of source nodes (in-degree 0) and sink nodes (out-degree 0) in the DAG. The answer is max(sources, sinks). The intuition is that every source needs at least one incoming edge and every sink needs at least one outgoing edge to create a single SCC. Special case: if the graph is already strongly connected (1 SCC), the answer is 0.\n\n---\n\n## Summary\n\nKosaraju's algorithm is an elegant two-pass DFS approach to finding all Strongly Connected Components in a directed graph. Here are the key takeaways:\n\n- An **SCC** is a maximal set of vertices where every vertex can reach every other vertex via directed paths.\n- **Kosaraju's three steps:** (1) DFS on original graph to get finish order, (2) transpose the graph, (3) DFS on transposed graph in reverse finish order.\n- **Why it works:** The finish order ensures \"source\" SCCs are processed first, and the transpose ensures DFS stays within a single SCC.\n- **Time complexity:** O(V + E). Space complexity: O(V + E).\n- **Kosaraju's vs Tarjan's:** Both are O(V + E). Kosaraju's is easier to understand but needs two passes and extra space for the transpose. Tarjan's uses one pass but is harder to implement.\n- **Applications:** Condensation graphs, 2-SAT, social network analysis, compiler optimization.\n- **Common mistake to avoid:** Pushing onto the stack at discovery time instead of finish time.\n\nIn the next chapter, we will look at other advanced graph algorithms that build on these concepts.\n\n---\n\n## References\n\n- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. *Introduction to Algorithms* (CLRS), Chapter 22: Elementary Graph Algorithms. MIT Press.\n- Sedgewick, R., & Wayne, K. *Algorithms, 4th Edition*, Section 4.2: Directed Graphs. Addison-Wesley. [https://algs4.cs.princeton.edu/42digraph/](undefined)\n- Sharir, M. (1981). \"A strong-connectivity algorithm and its applications in data flow analysis.\" *Computers & Mathematics with Applications*, 7(1), 67-72.\n- CP-Algorithms: Strongly Connected Components. [https://cp-algorithms.com/graph/strongly-connected-components.html](undefined)\n- Broder, A., et al. (2000). \"Graph structure in the Web.\" *Computer Networks*, 33(1-6), 309-320.","pageType":"dsa"}

Kosaraju's Algorithm

Ashish Pratap Singh

Get Premium