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.
Could you write a function to identify and return all safe nodes in the graph, sorted in ascending order? How would you approach this problem, considering efficiency and edge cases?
Given a directed graph of n
nodes labeled from 0
to n - 1
, where the graph is represented by a 0-indexed 2D integer array graph
, where graph[i]
is an array of nodes adjacent to node i
, indicating an edge from node i
to each node in graph[i]
. A node is a terminal node if it has 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). The task is to return a sorted array of all the safe nodes in the graph.
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
The brute force approach involves performing a Depth-First Search (DFS) from each node to check if all paths lead to a terminal node. For each node, explore all possible paths. If a cycle is detected, then the node is not safe. If all paths end in terminal nodes, then the node is safe.
i
from 0
to n - 1
:i
.visited
set to detect cycles.i
lead to terminal nodes without cycles, then node i
is safe.def is_safe_node_brute_force(graph, node, visited, path):
visited[node] = True
path[node] = True
for neighbor in graph[node]:
if path[neighbor]:
return False # Cycle detected
if not visited[neighbor]:
if not is_safe_node_brute_force(graph, neighbor, visited, path):
return False
path[node] = False # Backtrack: remove node from current path
return True
def safe_nodes_brute_force(graph):
n = len(graph)
safe_nodes = []
for i in range(n):
visited = [False] * n
path = [False] * n
if is_safe_node_brute_force(graph, i, visited, path):
safe_nodes.append(i)
return sorted(safe_nodes)
O(n * (V + E)), where n is the number of nodes, V is the number of vertices, and E is the number of edges. For each node, we may have to traverse the entire graph.
O(n) due to the visited
and path
arrays and the recursion stack in the worst case.
The optimal approach involves reversing the graph and using topological sorting. A node is safe if all the nodes that lead to it are safe. By reversing the graph, we can identify terminal nodes in the reversed graph, which were nodes that other nodes led into.
from collections import deque
def safe_nodes_optimal(graph):
n = len(graph)
reversed_graph = [[] for _ in range(n)]
in_degree = [0] * n
for i in range(n):
for neighbor in graph[i]:
reversed_graph[neighbor].append(i)
in_degree[i] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
safe_nodes = []
while queue:
node = queue.popleft()
safe_nodes.append(node)
for neighbor in reversed_graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return sorted(safe_nodes)
O(V + E), where V is the number of vertices and E is the number of edges, because reversing the graph and Kahn's algorithm both take O(V+E) time.
O(V + E) to store the reversed graph, in-degree array, and the queue.