Course schedule (cycle detection)

Decide whether every course can be finished. A directed graph can be fully ordered only if it has no cycle.

The idea

Colour every node white (unvisited). DFS from each white node, turning it grey (in progress) on entry and black (done) on exit. A grey node reached again means the recursion has looped back onto its own path, which is exactly a cycle. A black node is already proven safe and is never revisited.

Code

public static bool CanFinish(int n, Dictionary<char, List<char>> graph) {
    var state = new Dictionary<char, int>(); // 0 unvisited, 1 in progress, 2 done
    foreach (var u in graph.Keys)
        if (state.GetValueOrDefault(u) == 0 && HasCycle(u, graph, state))
            return false;
    return true;
}

static bool HasCycle(char u, Dictionary<char, List<char>> graph, Dictionary<char, int> state) {
    state[u] = 1; // in progress: sits on the current recursion path
    foreach (char v in graph[u]) {
        int s = state.GetValueOrDefault(v);
        if (s == 1) return true; // back edge to a grey node: a cycle
        if (s == 0 && HasCycle(v, graph, state)) return true;
    }
    state[u] = 2; // done: can never sit on a cycle
    return false;
}

Tips

• Two colours are not enough: you must tell "currently on this path" (grey) apart from "fully explored, definitely safe" (black).
• Kahn's algorithm (the topological sort lesson) detects the same thing by counting how many nodes make it into the order.

In the .NET library

A back edge to a grey node is the one and only sign of a cycle in a directed graph. An edge to a black node is always safe, even if it looks like it "goes backwards" in the recursion.