Problem 23.4 · Cycle DetectionMedium

Find Eventual Safe States

PatternGraph DFS and Flood Fill Topological Sort

What it teaches: Colours as results: a node is safe when every path from it ends, i.e. it can't reach a cycle.

Practise it on judges as “Find Eventual Safe States”.

The problem

In a directed graph (graph[i] = successors of i), a node is safe if every path starting from it leads to a terminal node (one with no outgoing edges). Return all safe nodes in ascending order.

Example 1

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2, 4, 5, 6]

Constraints

1 ≤ n ≤ 10⁴

Pattern clues in the wording

→ Nodes that can't reach a cycle

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	graph = [[1,2],[2,3],[5],[0],[5],[],[]]	[2,4,5,6]
2	graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]	[4]

From slow to fast

Approaches

1. Three-colour DFS · O(V + E)

Three-colour DFS

Time O(V + E) Space O(V)

safe(u): if coloured, return colour == black. Mark grey; if any successor is unsafe, return false (leave grey). Else mark black.

Approach 1

import java.util.*;

class Solution {
    private int[] state;

    public List<Integer> eventualSafeNodes(int[][] graph) {
        state = new int[graph.length];
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) if (safe(graph, i)) out.add(i);
        return out;
    }

    private boolean safe(int[][] g, int u) {
        if (state[u] != 0) return state[u] == 2;
        state[u] = 1;
        for (int v : g[u]) if (!safe(g, v)) return false;
        state[u] = 2;
        return true;
    }
}

Verdict: Each node is resolved once.

Before you submit

Edge cases and common mistakes

Test these inputs

Self-loop
All nodes terminal

Mistakes people make

Resetting a node to white after finding a cycle (loses the information).

Interview

Follow-up questions

How does Kahn's algorithm solve it?

Command Palette

The problem

Approaches

Three-colour DFS

Edge cases and common mistakes

Follow-up questions