Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
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) = 7
edges (int[][]) = [[0,1],[0,2],[1,2],[1,3],[2,5],[3,0],[4,5]]
size (int) = 7
Return:
(int) 4
Example 2
Input:
nodes (int) = 4
edges (int[][]) = [[0,1],[1,2],[2,3]]
size (int) = 3
Return:
(int) 4
Example 3
Input:
nodes (int) = 3
edges (int[][]) = [[0,1],[1,2],[2,0]]
size (int) = 3
Return:
(int) 0

Use 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 answer
Run your code to see the result.