My approach was by flipping the perspective of the graph. Instead of working with the original graph, I created a reversed graph, where edges point from their destination back to their source. This allows me to process nodes starting from the terminal ones (nodes with no outgoing edges), which are inherently safe.
Next, I calculated the out-degree for each node in the original graph, which represents the number of edges each node has. Nodes with an out-degree of 0 are terminal nodes, so I added them to a queue to process them first.
From there, I processed the queue. For each node, I marked it as safe and updated its neighbors in the reversed graph. If a neighbor’s out-degree dropped to 0, I added it to the queue since it had no remaining paths leading to unsafe nodes. This way, I worked backward, ensuring only nodes that eventually lead to terminal nodes were marked as safe.
Finally, I gathered all the safe nodes, sorted them, and returned the result.
from collections import deque, defaultdict
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
n = len(graph)
reverse_graph = defaultdict(list)
in_degree = [0] * n
for src in range(n):
for dest in graph[src]:
reverse_graph[dest].append(src)
in_degree[src] = len(graph[src])
queue = deque([i for i in range(n) if in_degree[i] == 0])
safe_nodes = set(queue)
while queue:
node = queue.popleft()
for neighbor in reverse_graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
safe_nodes.add(neighbor)
return sorted(safe_nodes)- Time: O(V + E) where V is the number of nodes (vertices) in the graph and E is the number of edges in the graph.
- Space: O(V + E) where V is the number of nodes (vertices) in the graph and E is the number of edges in the graph.
