Find Eventual Safe States
Problem link: https://leetcode.com/problems/find-eventual-safe-states/
Problem Statement
There is a directed graph of n nodes with each node labeled from 0 to n - 1. A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).
Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
Input
A 2D integer array graph where graph[i] is an array of nodes adjacent to node i.
Output
A sorted list of integers representing safe nodes.
Example
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]] Output: [2,4,5,6] Explanation: Nodes 5 and 6 are terminal nodes. Node 2 and 4 only point to node 5, so they are safe. Nodes 0, 1, and 3 are part of a cycle and are not safe.
Explanation
Nodes 5 and 6 have no outgoing edges (terminal). Node 2 points to 5 (safe). Node 4 points to 5 (safe). Nodes 0, 1, and 3 form a cycle; you can be stuck there forever, so they aren't safe.
Brute Force
Intuition
For every node, use DFS to explore all possible paths. If any path enters a cycle or fails to reach a terminal node, the starting node is not safe.
Approach
- For each node i from 0 to n-1:
- Perform DFS to check if a cycle is reachable.
- Keep track of visited nodes in the current path.
- If a node is part of a cycle, mark it as unsafe.
Optimal Solution
Intuition
A node is safe if it doesn't lead to a cycle. By reversing all edges, terminal nodes (out-degree 0) become start nodes (in-degree 0). We can then use Kahn's Algorithm to gradually remove nodes that lead only to safe nodes.
Approach
- Reverse the Graph: Create a new adjacency list where every edge (u -> v) becomes (v -> u).
- In-Degree Array: Calculate the in-degree of all nodes in this reversed graph (this is equivalent to the out-degree in the original graph).
- Queue Terminal Nodes: Add all nodes with in-degree 0 to a queue.
- BFS (Kahn's):
- Pop node
u(it is safe). - For each neighbor
vofuin the reversed graph:- Decrement
indegree[v]. - If
indegree[v] == 0, it means all paths fromvin the original graph now lead to safe nodes. Addvto the queue.
- Decrement
- Pop node
- Sort & Return: Sort the collected safe nodes.
Code (Java)
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
List<List<Integer>> reverseAdj = new ArrayList<>();
int[] indegree = new int[n];
for (int i = 0; i < n; i++) reverseAdj.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
for (int neighbor : graph[i]) {
// Original: i -> neighbor | Reverse: neighbor -> i
reverseAdj.get(neighbor).add(i);
indegree[i]++;
}
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) q.add(i);
}
boolean[] safe = new boolean[n];
while (!q.isEmpty()) {
int curr = q.poll();
safe[curr] = true;
for (int neighbor : reverseAdj.get(curr)) {
if (--indegree[neighbor] == 0) q.add(neighbor);
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (safe[i]) result.add(i);
}
return result;
}
}
Complexity Analysis
Time: Building the reverse graph takes O(V+E), and the BFS processes each node and edge once. Sorting the result takes O(V log V), but usually V is small enough that O(V+E) dominates. Space: O(V+E) for the reversed adjacency list.
Quick Revision (Brute Force)
- DFS from every node to detect cycles.
- Inefficient due to repeated path traversals.
Quick Revision (Optimal)
- Safe nodes = nodes not in or leading to a cycle.
- Reverse graph to turn 'out-degree 0' into 'in-degree 0'.
- Use Kahn's Algorithm (BFS) to propagate 'safeness' backwards.
- Remaining nodes with in-degree > 0 are part of cycles.