Proficient Level
Implement the eventualSafeNodesCount method that counts nodes that cannot reach a cycle.
You are given a directed graph as edge pairs [from, to]. A node is eventually safe if every path starting from it ends at a terminal node and never gets trapped in a cycle.
Return the number of eventually safe nodes in the graph.
Example 1
Input
nodes (int) =
7edges (int[][]) =
[[0,1],[0,2],[1,2],[1,3],[2,5],[3,0],[4,5]]size (int) =
7Returns (int)
4Example 2
Input
nodes (int) =
4edges (int[][]) =
[[0,1],[1,2],[2,3]]size (int) =
3Returns (int)
4Example 3
Input
nodes (int) =
3edges (int[][]) =
[[0,1],[1,2],[2,0]]size (int) =
3Returns (int)
0Use DFS with coloring to detect whether a node can reach a cycle.
Mark a node as visiting while exploring it. If DFS reaches a visiting node again, a cycle exists. A node is safe only if all of its outgoing neighbors are safe. Once a node's result is known, store it so it is not recalculated.
The count of safe nodes is the final answer.
Pseudocode:
function eventualSafeNodesCount(nodes, edges, size):
build graph
color = array filled with 0
function isSafe(node):
if color[node] != 0:
return color[node] == 2
color[node] = 1
for each next in graph[node]:
if not isSafe(next):
return false
color[node] = 2
return true
answer = 0
for node from 0 to nodes - 1:
if isSafe(node):
answer++
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run