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:
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.length1 <= n <= 1040 <= graph[i].length <= n0 <= graph[i][j] <= n - 1graph[i] is sorted in a strictly increasing order.[1, 4 * 104].This approach utilizes the concept of reversing the graph and then performing a topological sort. Essentially, if we consider nodes leading to terminal nodes in the original graph, these nodes can be treated as terminal nodes in the reversed graph. We perform a topological sort to find such nodes.
By processing nodes which have no outgoing edges in the reversed graph (these correspond to safe nodes in the original graph), we can iteratively determine more nodes that are safe.
The function findEventualSafeNodes reverses the input graph and employs a topological sorting method to determine the safe nodes.
For simplicity, you will need to manage node degrees and process the graph using a queue (BFS style). Nodes that have no incoming edges left are safe.
Java
Python
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is due to the graph traversal.
Space Complexity: O(V) for storing the reversed graph and the in-degrees array.
This approach adopts a classic depth-first search (DFS) to identify which nodes are safe. Safe nodes are marked during traversal.
We maintain a visited state for each node: unvisited, visiting, or safe. During DFS traversal, if we encounter a node marked as visiting, a cycle is detected, and the path is unsafe.
The function leverages DFS to maintain a status for each node: safe, unsafe, or unknown. It handles cycles efficiently by marking nodes actively being visited and recording safe nodes on successful completion of DFS for a node.
C#
JavaScript
Time Complexity: O(V + E), as each node and each edge is examined only once.
Space Complexity: O(V) for the recursion stack and state storage.
| Approach | Complexity |
|---|---|
| Approach 1: Reverse Graph and Topological Sort | Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is due to the graph traversal. Space Complexity: O(V) for storing the reversed graph and the in-degrees array. |
| Approach 2: Depth-First Search with Safe Node Identification | Time Complexity: O(V + E), as each node and each edge is examined only once. Space Complexity: O(V) for the recursion stack and state storage. |
G-20. Find Eventual Safe States - DFS • take U forward • 214,476 views views
Watch 9 more video solutions →Practice Find Eventual Safe States with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor