# Find Eventual Safe States **Difficulty:** MEDIUM [External](https://leetcode.com/problems/find-eventual-safe-states) Canonical: https://scaleengineer.com/dsa/problems/find-eventual-safe-states **Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort) **Data structures:** Graph --- ## Problem There is a directed graph of `n` nodes with each node labeled from `0` to `n - 1`. The graph is represented by a **0-indexed** 2D integer array `graph` where `graph[i]` is an integer array of nodes adjacent to node `i`, meaning there is an edge from node `i` to each node in `graph[i]`. 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. **Example 1:** ![Illustration of graph](https://assets.glich.co/dsa/find-eventual-safe-states/image0.png) **Input:** graph = [[1,2],[2,3],[5],[0],[5],[],[]] **Output:** [2,4,5,6] **Explanation:** The given graph is shown above. Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them. Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6. **Example 2:** **Input:** graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] **Output:** [4] **Explanation:** Only node 4 is a terminal node, and every path starting at node 4 leads to node 4. **Constraints:** * `n == graph.length` * `1 <= n <= 104` * `0 <= graph[i].length <= n` * `0 <= graph[i][j] <= n - 1` * `graph[i]` is sorted in a strictly increasing order. * The graph may contain self-loops. * The number of edges in the graph will be in the range `[1, 4 * 104]`. # Approaches ## Naive Depth-First Search This approach checks each node one by one to determine if it's a safe state. For every node, it initiates a new Depth-First Search (DFS) to explore all possible paths starting from it. During the DFS, it keeps track of the nodes in the current path to detect cycles. If a path encounters a node that is already in the current path, a cycle is found, and the starting node is deemed unsafe. If all paths from the starting node end in terminal nodes, it's considered safe. The main drawback is the massive amount of redundant computation, as the safety of a node might be re-evaluated multiple times across different initial DFS calls. **Time:** O(N * (N + E)) in a graph with no sharing of paths, but can be as bad as O(N * N!) in graphs with many paths. This is because for each of the N nodes, we might traverse a significant portion of the graph, leading to repeated work. For instance, in a dense DAG, the number of paths can be exponential. · **Space:** O(N), where N is the number of nodes. This is for the recursion stack depth and the `path` set, which can store up to N nodes in the case of a long path. **Pros:** Conceptually simple and a direct translation of the problem definition. **Cons:** Extremely inefficient due to re-computation.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints. ### Explanation The algorithm iterates through every node in the graph and, for each one, performs a full DFS traversal to verify its safety. A helper function, `isSafe(node, path)`, is used for this purpose. The `path` set is crucial for detecting cycles within a single traversal. If the DFS for a node `u` encounters a neighbor `v` that is already in the `path`, it signifies a cycle, making `u` unsafe. If a neighbor `v` is found to be unsafe through a recursive call, `u` is also marked as unsafe. A node is only safe if all its outgoing paths exclusively lead to terminal nodes. Because this method doesn't use memoization, the safety status of a single node might be computed over and over again if it's reachable from multiple starting nodes, leading to an exponential time complexity in the worst-case scenarios. ```java import java.util.*; class Solution { public List eventualSafeNodes(int[][] graph) { List safeNodes = new ArrayList<>(); for (int i = 0; i < graph.length; i++) { if (isSafe(i, graph, new HashSet<>())) { safeNodes.add(i); } } return safeNodes; } private boolean isSafe(int node, int[][] graph, Set path) { if (path.contains(node)) { // Cycle detected return false; } if (graph[node].length == 0) { // Terminal node return true; } path.add(node); for (int neighbor : graph[node]) { if (!isSafe(neighbor, graph, path)) { // Path to an unsafe node or cycle path.remove(node); // Backtrack return false; } } path.remove(node); // Backtrack return true; } } ``` ### Algorithm 1. Iterate through each node `i` from `0` to `n-1` to check if it's a safe node. 2. For each node `i`, start a Depth-First Search (DFS). To do this, call a helper function, say `isSafe(currentNode, path)`. The `path` parameter is a set that keeps track of all nodes in the current traversal path from the starting node `i` to `currentNode`. 3. Inside the `isSafe` function: a. If `currentNode` is already in `path`, it means we have detected a cycle. A node in a cycle is not safe. Return `false`. b. If `currentNode` is a terminal node (no outgoing edges), it's safe by definition. Return `true`. c. Add `currentNode` to the `path` set to mark it as part of the current recursion stack. d. Recursively call `isSafe` for all neighbors of `currentNode`. If any of these recursive calls return `false`, it means `currentNode` can lead to an unsafe path. Immediately return `false`. e. If all neighbors lead to safe paths, then `currentNode` is safe. Before returning, remove `currentNode` from `path` (backtracking). f. Return `true`. 4. If the initial call `isSafe(i, new HashSet<>())` returns `true`, add `i` to the list of safe nodes. 5. After checking all nodes, return the list of safe nodes. ## Topological Sort on Reversed Graph This approach reframes the problem by looking at it from the perspective of terminal nodes. A node is safe if all its paths lead to a terminal node. This suggests we can work backward from the terminal nodes. The algorithm identifies all nodes that eventually lead to terminal nodes, which are precisely the safe nodes. Nodes involved in cycles or that can reach cycles will never have their out-degrees reduced to zero in this process. This is effectively performing a topological sort on the graph. We start with nodes that have no outgoing edges (terminal nodes). We then iteratively 'peel off' these safe nodes and update the nodes that point to them. If a node's all outgoing edges point to nodes that have been peeled off, it too becomes safe and is added to our set. **Time:** O(N log N + E). Building the reversed graph and initializing out-degrees takes O(N + E). The while loop processes each node and edge once, also taking O(N + E). The final sorting step takes O(N log N). Overall, the complexity is dominated by O(N + E) if E is large, or O(N log N) if E is small. · **Space:** O(N + E), where N is the number of nodes and E is the number of edges. This space is used for storing the reversed graph (`revGraph`), the `outDegree` array, and the queue. **Pros:** A correct and reasonably efficient approach.; Avoids deep recursion, which can be an issue in some environments.; The logic is closely related to the well-known Kahn's algorithm for topological sorting. **Cons:** Requires O(N + E) extra space to store the reversed graph, which can be significant.; Requires a final sorting step, which adds an O(N log N) time component. ### Explanation The core idea is to reverse the graph's edges and use a variation of Kahn's algorithm for topological sorting. First, we compute the out-degree of every node in the original graph. All nodes with an out-degree of 0 are terminal nodes and are, by definition, safe. We add them to a queue. Then, we process the queue. When we dequeue a node `u`, we know it's safe. We then look at the reversed graph to find all nodes `v` that had an edge to `u`. For each such `v`, we decrement its out-degree. This signifies that one of its outgoing paths has been resolved to a safe conclusion. If `v`'s out-degree drops to 0, it means all of its outgoing paths lead to nodes that are now known to be safe. Thus, `v` itself becomes a safe node, and we add it to the queue. We continue this until the queue is empty. The nodes that were added to the queue at any point are the safe nodes. Finally, we sort the resulting list. ```java import java.util.*; class Solution { public List eventualSafeNodes(int[][] graph) { int n = graph.length; List> revGraph = new ArrayList<>(); for (int i = 0; i < n; i++) { revGraph.add(new ArrayList<>()); } int[] outDegree = new int[n]; for (int i = 0; i < n; i++) { outDegree[i] = graph[i].length; for (int neighbor : graph[i]) { revGraph.get(neighbor).add(i); } } Queue queue = new LinkedList<>(); for (int i = 0; i < n; i++) { if (outDegree[i] == 0) { queue.offer(i); } } List safeNodes = new ArrayList<>(); while (!queue.isEmpty()) { int u = queue.poll(); safeNodes.add(u); for (int v : revGraph.get(u)) { outDegree[v]--; if (outDegree[v] == 0) { queue.offer(v); } } } Collections.sort(safeNodes); return safeNodes; } } ``` ### Algorithm 1. **Reverse the Graph**: Create an adjacency list `revGraph` that represents the graph with all its edges reversed. If `u -> v` is an edge in the original graph, `v -> u` will be an edge in `revGraph`. 2. **Calculate Out-Degrees**: Create an array `outDegree` of size `n`. Iterate through the original `graph` and for each node `i`, `outDegree[i]` will be `graph[i].length`. 3. **Initialize Queue**: Create a queue and add all terminal nodes from the original graph to it. Terminal nodes are those with an out-degree of 0. 4. **Process Nodes (Kahn's Algorithm)**: a. While the queue is not empty, dequeue a node `u`. b. This node `u` is a safe node. Add it to a result list. c. For each neighbor `v` of `u` in `revGraph` (these are the nodes that originally pointed to `u`): i. Decrement `outDegree[v]`. ii. If `outDegree[v]` becomes 0, it means all of `v`'s outgoing paths now lead to nodes we have processed and confirmed as safe. Therefore, `v` is also safe. Enqueue `v`. 5. **Finalize Result**: The list of nodes collected during the process contains all safe nodes. Sort this list in ascending order and return it. ## Depth-First Search with Coloring This approach identifies safe nodes by finding all nodes that are *not* unsafe. A node is unsafe if it's part of a cycle or can reach a cycle. We can find all such nodes using a single Depth-First Search (DFS) traversal over the graph, augmented with a 3-state coloring scheme to keep track of the status of each node. - **WHITE (0)**: The node has not been visited yet. - **GRAY (1)**: The node is currently being visited (i.e., it's in the current recursion stack). - **BLACK (2)**: The node and all of its descendants have been visited, and it's confirmed to be a safe node. If the DFS traversal from a node encounters a GRAY node, it has found a cycle. All nodes in the current recursion path (which are also GRAY) are part of or can reach this cycle, so they are unsafe. A node is marked BLACK only when all paths from it are confirmed to lead to other BLACK nodes or terminal nodes. **Time:** O(N + E), where N is the number of nodes and E is the number of edges. Each node is visited once. During the visit, we iterate through its neighbors. Therefore, every node and every edge is processed a constant number of times. · **Space:** O(N), where N is the number of nodes. This space is for the `color` array and the recursion stack for DFS. **Pros:** Optimal time complexity of O(N + E).; Optimal space complexity of O(N).; Each node's state is computed only once due to memoization with the color array. **Cons:** The concept of three states (colors) can be slightly more complex to understand initially compared to other graph traversal algorithms. ### Explanation The algorithm uses a single `color` array to memoize the state of each node, avoiding redundant computations. We iterate through all nodes. If a node is unvisited (WHITE), we start a DFS from it. The DFS function, `isSafe`, first marks the current node as visiting (GRAY). Then, it explores its neighbors. If it finds a GRAY neighbor, a cycle is detected, and the node is unsafe. If it finds a WHITE neighbor, it recursively explores it. If the recursive call reveals that the neighbor is unsafe, the current node is also unsafe. If a neighbor is BLACK, we know it's a safe path and continue. If all neighbors are processed without finding an unsafe path, the current node is marked as safe (BLACK). After checking all nodes, we simply collect all nodes marked as BLACK into our result list, which will be sorted because we iterate from 0 to n-1. ```java import java.util.*; class Solution { public List eventualSafeNodes(int[][] graph) { int n = graph.length; // 0: unvisited (WHITE) // 1: visiting (GRAY) // 2: visited and safe (BLACK) int[] color = new int[n]; for (int i = 0; i < n; i++) { if (color[i] == 0) { isSafe(i, graph, color); } } List safeNodes = new ArrayList<>(); for (int i = 0; i < n; i++) { if (color[i] == 2) { safeNodes.add(i); } } return safeNodes; } // Returns true if the node is safe, false otherwise private boolean isSafe(int node, int[][] graph, int[] color) { // Mark as visiting color[node] = 1; // GRAY for (int neighbor : graph[node]) { if (color[neighbor] == 1) { // Cycle detected return false; } if (color[neighbor] == 0) { // If neighbor is unvisited, perform DFS. If it's unsafe, this node is also unsafe. if (!isSafe(neighbor, graph, color)) { return false; } } // If color[neighbor] is 2 (BLACK), it's a known safe node, so we continue. } // All paths from this node are safe color[node] = 2; // BLACK return true; } } ``` ### Algorithm 1. **Initialize State**: Use a `color` array of size `n` to keep track of the state of each node. `0` (WHITE) for unvisited, `1` (GRAY) for currently visiting (in the recursion stack), and `2` (BLACK) for visited and confirmed to be safe. 2. **Iterate and DFS**: Iterate through each node `i` from `0` to `n-1`. a. If `color[i]` is WHITE (0), it means we haven't determined its safety yet. Start a DFS from this node by calling a helper function `isSafe(i, color, graph)`. 3. **`isSafe` DFS Helper Function**: a. Mark the current node as visiting: `color[node] = 1` (GRAY). b. For each `neighbor` of the current `node`: i. If `color[neighbor]` is GRAY (1), we've found a back edge to a node in the current recursion path. This means there is a cycle. The current node can reach this cycle, so it's unsafe. Return `false`. ii. If `color[neighbor]` is WHITE (0), recursively call `isSafe(neighbor, ...)`. - If the recursive call returns `false`, it means the neighbor is part of a cycle or leads to one. Propagate this result by returning `false` immediately. iii. If `color[neighbor]` is BLACK (2), it's a known safe node, so we can safely ignore it and continue to the next neighbor. c. If the loop over neighbors completes without returning `false`, it means the current node does not lead to any cycles. It is a safe node. d. Mark the node as fully explored and safe: `color[node] = 2` (BLACK). e. Return `true`. 4. **Collect Results**: After the main loop finishes, iterate from `0` to `n-1`. Any node `i` with `color[i] == 2` is a safe node. Add it to the result list. The result will be naturally sorted. # Solutions ### Java ```java class Solution { private int[] color; private int[][] g; public List eventualSafeNodes(int[][] graph) { int n = graph.length; color = new int[n]; g = graph; List ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { if (dfs(i)) { ans.add(i); } } return ans; } private boolean dfs(int i) { if (color[i] > 0) { return color[i] == 2; } color[i] = 1; for (int j : g[i]) { if (!dfs(j)) { return false; } } color[i] = 2; return true; } } ``` ### JavaScript ```javascript /** * @param {number[][]} graph * @return {number[]} */ var eventualSafeNodes = function (graph) { const n = graph.length; const color = new Array(n).fill(0); function dfs(i) { if (color[i]) { return color[i] == 2; } color[i] = 1; for (const j of graph[i]) { if (!dfs(j)) { return false; } } color[i] = 2; return true; } let ans = []; for (let i = 0; i < n; ++i) { if (dfs(i)) { ans.push(i); } } return ans; }; ``` ### CPP ```cpp class Solution { public: vector color; vector eventualSafeNodes(vector> &graph) { int n = graph.size(); color.assign(n, 0); vector ans; for (int i = 0; i < n; ++i) if (dfs(i, graph)) ans.push_back(i); return ans; } bool dfs(int i, vector> &g) { if (color[i]) return color[i] == 2; color[i] = 1; for (int j : g[i]) if (!dfs(j, g)) return false; color[i] = 2; return true; } }; ``` ### Python ```python class Solution: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: def dfs(i): if color[i]: return color[i] == 2 color[i] = 1 for j in graph[i]: if not dfs(j): return False color[i] = 2 return True n = len(graph) color = [0] * n return [i for i in range(n) if dfs(i)] ```