802. Find Eventual Safe States

Depth-First Search Breadth-First Search Graph Topological Sort Memoization

Time: O(V+E)

Space: O(V)

Intuition

A node is safe if it's not part of a cycle and can't reach a cycle. Use DFS with states: unvisited, in-progress, safe, unsafe.

Algorithm

1For each unvisited node, DFS to detect cycles.
2Mark node as in-progress. Recurse on neighbors. If any neighbor is in-progress → cycle → unsafe.
3After all neighbors processed without cycle: mark safe.
4Return all safe nodes sorted.

Common Pitfalls

•Memoize: once a node is marked safe/unsafe, don't re-visit. Terminal nodes (out-degree 0) are automatically safe.

802.cs

// Approach: DFS with 3-state coloring (init/visiting/visited); a node is safe if DFS completes without entering a cycle.
// Time: O(V+E) Space: O(V)

enum State { kInit, kVisiting, kVisited }

public class Solution
{
    public IList<int> EventualSafeNodes(int[][] graph)
    {
        List<int> ans = new List<int>();
        State[] states = new State[graph.Length];

        for (int i = 0; i < graph.Length; ++i)
        {
            if (!HasCycle(graph, i, states))
                ans.Add(i);
        }

        return ans;
    }

    private bool HasCycle(int[][] graph, int u, State[] states)
    {
        if (states[u] == State.kVisiting)
            return true;
        if (states[u] == State.kVisited)
            return false;

        states[u] = State.kVisiting;
        foreach (var v in graph[u])
        {
            if (HasCycle(graph, v, states))
                return true;
        }
        states[u] = State.kVisited;

        return false;
    }
}

Was this solution helpful?