Problem Description
Given a directed graph represented by a 0-indexed 2D integer array where each node has edges to adjacent nodes, a node is termed a "terminal node" if it has no outgoing edges. A "safe node" is defined as a node from which every possible path leads to a terminal node or another safe node. The task is to return an array of all safe nodes sorted in ascending order.
Key Insights
- Nodes with no outgoing edges are terminal nodes and are inherently safe.
- A node can be classified as safe if every path starting from it leads to a terminal node.
- This problem can be approached using Depth-First Search (DFS) or Topological Sort to explore nodes and determine safety.
- The graph may contain cycles, which need to be handled to avoid infinite loops.
Space and Time Complexity
Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. Each node and edge is processed once. Space Complexity: O(V), for the storage of the visited status and recursion stack in DFS.
Solution
To solve this problem, we can use Depth-First Search (DFS) to explore each node. We maintain a status for each node indicating whether it is safe, unsafe, or unvisited. Starting from terminal nodes (which are safe), we recursively mark nodes as safe if all their neighbors lead to safe nodes. If a cycle is detected during the DFS traversal, those nodes are marked as unsafe. Finally, we return the sorted list of safe nodes.