Find Eventual Safe States

mediumGraphs: Topological Sort & Union-Find111 stepsJava · Python · C++

A node is safe if every path from it ends at a terminal node (no outgoing edges). Reverse the edges and run Kahn's algorithm from the terminal nodes: a node becomes safe once all of its outgoing edges lead to safe nodes.

▶ Watch the animated trace

Traced input: graph = [[1, 2], [2, 3], [5], [0], [5], [], []] → [2, 4, 5, 6]. Original problem: leetcode.com/problems/find-eventual-safe-states/

Complexity

BestO(V + E)

AverageO(V + E)

WorstO(V + E)

SpaceO(V + E)

Building the reverse graph and the BFS are both linear.

Key idea

Terminal nodes are safe by definition.
Count each node's outgoing edges (its out-degree).
When a safe node is confirmed, every node pointing to it loses one unresolved edge.
A node whose count hits 0 is safe; nodes on or leading into cycles never get there.

Common mistakes

Forgetting to sort the output.
DFS with colouring also works; recursion depth can be an issue on long chains.

Solution

Java

List<Integer> eventualSafeNodes(int[][] graph) {
    int n = graph.length;
    List<List<Integer>> rev = new ArrayList<>();
    for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
    int[] out = new int[n];
    for (int u = 0; u < n; u++) {
        out[u] = graph[u].length;
        for (int v : graph[u]) rev.get(v).add(u);
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (out[i] == 0) queue.offer(i);
    boolean[] safe = new boolean[n];
    while (!queue.isEmpty()) {
        int v = queue.poll();
        safe[v] = true;
        for (int u : rev.get(v)) {
            if (--out[u] == 0) queue.offer(u);
        }
    }
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < n; i++) if (safe[i]) res.add(i);
    return res;
}

Python

def eventualSafeNodes(graph: List[List[int]]) -> List[int]:
    n = len(graph)
    rev = [[] for _ in range(n)]
    out = [len(g) for g in graph]
    for u in range(n):
        for v in graph[u]: rev[v].append(u)
    queue = deque(i for i in range(n) if out[i] == 0)
    safe = [False] * n
    while queue:
        v = queue.popleft()
        safe[v] = True
        for u in rev[v]:
            out[u] -= 1
            if out[u] == 0: queue.append(u)
    return [i for i in range(n) if safe[i]]

C++

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> rev(n);
    vector<int> out(n);
    for (int u = 0; u < n; u++) {
        out[u] = graph[u].size();
        for (int v : graph[u]) rev[v].push_back(u);
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (out[i] == 0) q.push(i);
    vector<bool> safe(n);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        safe[v] = true;
        for (int u : rev[v]) {
            if (--out[u] == 0) q.push(u);
        }
    }
    vector<int> res;
    for (int i = 0; i < n; i++) if (safe[i]) res.push_back(i);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Everything is a cycle No terminal nodes to start from.	`graph = [[1], [0]]`	`[]`
No edges Every node is terminal.	`graph = [[], [], []]`	`[0, 1, 2]`
Self loop Node 0 loops on itself forever.	`graph = [[0], []]`	`[1]`