Where it runs
1. The problem
You have a graph and one question about it: is there a path that leaves a node, passes through other nodes and comes back to where it started? Such a loop is called a cycle. A road map where you can drive in a circle has one. A family tree does not.
You already know how to walk a graph: breadth-first with a queue (step 88), and depth-first, where you follow one path to its end and then back up (step 89). A walk answers the cycle question right away. If during the walk you come to a node where you have already been, you may have found a loop.
The hard part is the word "may". The exact rule is different for the two kinds of graph, and a wrong rule finds cycles where there are none. This lesson goes through both rules.
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
Problems that ask whether a graph has a loop, such as dependencies that wait on each other. In a directed graph a neighbour still on the DFS stack closes a cycle, and in an undirected one any visited neighbour except the parent does.
Prerequisites are directed edges, and the courses can be finished exactly when the lesson's directed check finds no cycle.
Cells with the same letter are an undirected graph, and the parent check from the planted bug decides the answer.
Run the directed check with three states, and a node is safe when its DFS finishes without meeting a node still on the stack.
Each node has at most one outgoing edge, so walk from every unvisited node, store the step at which you saw each node, and a repeat on the current walk gives the cycle length.