DSA Notes

Graphs

Strongly Connected Components

Groups of vertices that can all reach each other.

The idea

In a directed graph, a strongly connected component is a largest set of vertices where every one can reach every other.

Tarjan’s algorithm finds them in one DFS. Vertices go on a stack as they are visited, with the same num and low as for bridges. When low[u] == num[u], u is the root of a component: pop the stack down to u.

Shrinking every component to a single vertex leaves a DAG, so topological order and DP apply. A fact that passes along edges (if one is true, all reachable ones are) is shared by a whole component.

Sample problem

2360. Longest Cycle in a Graph ↗ Hard

A directed graph has n nodes, and each node has at most one outgoing edge: edges[i] is the node that i points to, or −1. Return the length of the longest cycle, or −1 if there is none.

edges = [3,3,4,2,3]
output = 3   (2 → 4 → 3 → 2)

Why the solution works

On a cycle every node can reach every other, so a cycle lies inside one strongly connected component. And because each node has only one outgoing edge, a component with more than one node is exactly one cycle.

So the answer is the size of the largest strongly connected component that has at least two nodes.

Tarjan’s algorithm finds the components in one DFS: nodes wait on a stack, low tracks the earliest stacked node they can reach, and a node whose low equals its own visit time closes off a component.

Complexity: O(n) time and memory.

Watch out

  • Ignore edges into components that are already finished, or low becomes wrong.
  • Start a DFS from every unvisited vertex, not only vertex 1.
  • Deep graphs can overflow the recursion stack.
Watch it run

Practise on LeetCode