Where it runs
1. The problem
Earlier you counted connected groups in an undirected graph (step 91). There "connected" was simple: if there is a path between two people, they are in the same group. The path works both ways, because friendship goes both ways.
Now the edges have a direction. If node 0 points to node 1, that does not mean 1 points back to 0. One-way streets work the same way. Two junctions belong to one group only if you can drive from the first to the second AND back from the second to the first, following the direction of every street.
Such a group is called a strongly connected component (SCC). It is the largest group of nodes in which every node can reach every other node by following the edge directions. The task: given a directed graph, count how many SCCs it has.
A graph with no cycles at all splits into n components, one per node: you can move forward but never come back. A single directed cycle through every node is one component: you can ride it all the way around. Most graphs sit somewhere between those two extremes.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Directed graph problems about cycles and mutual reach, such as the longest cycle or how many nodes each start can visit. LeetCode rarely names strongly connected components, and two DFS passes, one on the graph and one on its reverse, find them in O(V + E).
Each node has at most one outgoing edge, so a component with more than one node is exactly one cycle, and the answer is the largest one.
Mark the nodes in a component of 2 or more nodes, or with an edge to itself. Every node that can reach a marked one is unsafe too.
Each node has one outgoing edge, so every node on a cycle visits exactly the cycle's length, and any other node visits one more than the node it points to.