Sponsored
Sponsored
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.
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.
1from collections import deque, defaultdict
2
3def eventualSafeNodes(graph):
4 G = defaultdict(list)
5 rg = defaultdict(list)
6 outdegree = [0] * len(graph)
7 for u in range(len(graph)):
8 for v in graph[u]:
9 G[u].append(v)
10 rg[v].append(u)
11 outdegree[u] = len(graph[u])
12
13 q = deque([])
14 for i in range(len(graph)):
15 if outdegree[i] == 0:
16 q.append(i)
17
18 res = []
19 while q:
20 u = q.popleft()
21 res.append(u)
22 for v in rg[u]:
23 outdegree[v] -= 1
24 if outdegree[v] == 0:
25 q.append(v)
26
27 return sorted(res)
28
29graph = [[1, 2], [2, 3], [5], [0], [5], [], []]
30print(eventualSafeNodes(graph))This function utilizes BFS with reversed graph edges. Nodes with zero out-degree in the reversed graph are safe, and propagating this information allows identification of additional safe nodes.
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.
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.
1var eventualSafeNodes = function(
This JavaScript implementation involves DFS with node marking: visiting, visited, or safe, similar to traditional cycle detection algorithms, ensuring each node is correctly classified as safe or part of an unsafe cycle.