# Part 20: Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm

### JB ・2 min read

CS Level Up Series (23 Part Series)

1) CS Level Up Series: Part 0
2) Part 1: Learning Dynamic Arrays
3 ... 21
3) Part 2: Learning Linked Lists
4) Part 3: Learning Stacks
5) Part 4: Learning Queues
6) Part 5: Learning Hash Tables
7) Part 6: Learning Binary Search Trees
8) Part 7: Learning Binary Heaps
9) Part 8: Learning Priority Queues
10) Part 9: Learning Graphs
11) Part 10: Learning Tries
12) Part 11: Learning Binary & Bit Manipulation
13) Part 12: Common Sorting Algorithms
14) Part 13: Searching Algorithms
15) Part 14: Permutations, Combinations, & Subsets
16) Part 15: NP-Complete & Fibonacci Heap
17) Part 16: Detecting Graph Cycles With Depth-First Search
18) Part 17: Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Part 18: Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Part 19: Finding Articulation Points & Bridges in Undirected Graphs
21) Part 20: Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Part 21: Checking If An Undirected Graph Is Bipartite
23) Part 22: Extending An Iterator

If you are unfamiliar with graphs, check out some of my earlier posts on them.

## Resources:

Takeaways:

- A
**strongly connected component**in a directed graph is a partition or sub-graph where each vertex of the component is reachable from every other vertex in the component. - Strongly connected components are always the
*maximal*sub-graph, meaning none of their vertices are part of another strongly connected component. - Finding strongly connected components is very similar to finding articulation points & bridges. Many of the solutions for finding them involve
**depth-first search**(DFS). - One way to find strongly connected components is using
**Tarjan's Algorithm**. - Tarjan's Algorithm uses DFS and a stack to find strongly connected components.
- The algorithm overview is:
- For every unvisited vertex
`V`

in the graph, perform DFS. - At the start of each DFS routine, mark the current vertex
`V`

as visited, push`V`

onto the stack, and assign`V`

an ID and low-link value. - Initially, like with articulation points & bridges, the ID and low-link values of
`V`

will be the same. - Increment the integer value we are using as the ID/low-link seed. So the next vertex
`W`

to enter our DFS routine will get a higher value for both (compared to`V`

). - For every adjacent vertex
`U`

of`V`

, if`U`

is unvisited, perform DFS (recursive call). - On exit of the recursive DFS call, or if
`U`

had already been visited, check if`U`

is on the stack. - If
`U`

is on the stack, update the low-link value of`V`

to be smallest between`low-link[V]`

and`low-link[U]`

- low-link represents the
*earliest*ancestor of a vertex (a lower value means the vertex entered DFS earlier). In other words, low-link is the ID of the earliest vertex`Y`

vertex`V`

is connected to.

- low-link represents the
- After exploring all adjacent vertices of
`V`

check if the ID of`V`

is the same as it's low-link value - If they are the same, then
`V`

is the root of a strongly connected component. - If they are the same, pop all vertices off the stack up to and including
`V`

. All of these vertices represent a single strongly connected component - Complete the above steps for the entire graph, and all strongly connected components will be discovered.

- For every unvisited vertex
- Time complexity of Tarjan's Algorithm is
`O(V + E)`

- where`V`

is the number of vertices, and`E`

the number of edges, in a graph. - Space is
`O(V)`

Below are implementations for finding strongly connected components in undirected adjacency list & adjacency matrix representations of graphs:

As always, if you found any errors in this post please let me know!

CS Level Up Series (23 Part Series)

1) CS Level Up Series: Part 0
2) Part 1: Learning Dynamic Arrays
3 ... 21
3) Part 2: Learning Linked Lists
4) Part 3: Learning Stacks
5) Part 4: Learning Queues
6) Part 5: Learning Hash Tables
7) Part 6: Learning Binary Search Trees
8) Part 7: Learning Binary Heaps
9) Part 8: Learning Priority Queues
10) Part 9: Learning Graphs
11) Part 10: Learning Tries
12) Part 11: Learning Binary & Bit Manipulation
13) Part 12: Common Sorting Algorithms
14) Part 13: Searching Algorithms
15) Part 14: Permutations, Combinations, & Subsets
16) Part 15: NP-Complete & Fibonacci Heap
17) Part 16: Detecting Graph Cycles With Depth-First Search
18) Part 17: Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Part 18: Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Part 19: Finding Articulation Points & Bridges in Undirected Graphs
21) Part 20: Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Part 21: Checking If An Undirected Graph Is Bipartite
23) Part 22: Extending An Iterator

Classic DEV Post from Dec 15 '19