101
0/320
Loading content...
You are given a directed graph represented as an adjacency list. The graph contains n nodes, labeled from 0 to n - 1, where graph[i] is a list of all nodes that node i has direct outgoing edges to.
A node is classified as a sink node (also called a terminal node) if it has no outgoing edges—meaning it is a dead-end from which you cannot travel further.
A node is classified as a safe node if and only if every possible path starting from that node eventually leads to a sink node (or to another safe node). In other words, a node is safe if you can never get stuck in an infinite loop starting from it—no matter which path you choose, you will always eventually reach a dead-end.
Your task is to identify and return all safe nodes in the graph. The result must be returned in ascending order of node labels.
Key Insight: A node is unsafe if and only if it is part of a cycle or can reach a cycle. If any path from a node leads into a cycle, that node cannot be safe because you could potentially follow that path and loop forever.
graph = [[1,2],[2,3],[5],[0],[5],[],[]][2,4,5,6]The graph has 7 nodes (0 through 6). Nodes 5 and 6 are sink nodes because they have no outgoing edges. Node 2 only points to node 5, so all paths from 2 lead to a sink—making it safe. Node 4 also only points to node 5, so it is safe. However, nodes 0, 1, and 3 form a cycle (0→1→3→0), so they are unsafe. Any path from these nodes could lead into this cycle.
graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]][4]Node 4 is the only sink node (no outgoing edges), and it is the only safe node. Nodes 0, 1, 2, and 3 are all connected to cycles: node 1 has a self-loop (1→1), and there's a cycle between nodes 0 and 3 (0→3→0).
graph = [[],[],[]][0,1,2]All three nodes are sink nodes with no outgoing edges. Since they are all dead-ends, they are all trivially safe—every path from them terminates immediately.
Constraints