Find eventually safe nodes in a directed graph

Updated

In a Directed Graph, we start at some random node and traverse the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.
Now, say our starting node is a safe node if and only if we must eventually walk to a terminal node.
i.e. u in the ordered pair {u, v} is said to be safe is and only if every path from u eventually leads to a terminal node.
Given: n (number of vertices/nodes) and edge list of graph
Print the array of nodes which are safe in sorted order.

Examples :

Input : n = 7, edges[] =
{ {0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 5}, {3, 0}, {4, 5} }
Output : {2, 4, 5, 6}
Terminal Nodes: {5, 6}
Safe Nodes: {2, 4}
              all paths from 2 lead to terminal nodes i.e. 2->5
              all paths from 4 lead to terminal nodes i.e 4->5

Input : n = 7, edges[] = { {0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 4},
                              {2, 6}, {2, 5}, {3, 0}, {4, 5} }
Output : {2, 4, 5, 6}
Terminal Nodes: {5, 6}
Safe Nodes: {2, 4}
              all paths from 2 lead to terminal nodes i.e. 2->5,
2->4->5, 2->6
              all paths from 4 also lead to terminal nodes i.e 4->5

Approach :

The main idea of the problem is whether you can reach a cycle from the node you start in.
1. If you can, then then the current node is not safe for all paths.
2. If you can’t, then after some finite number of steps you’ll stop i.e. it will be a safe node.
Thinking about this property more, a node is eventually safe if all its outgoing edges are to nodes that are eventually safe.
Let us perform a “brute force”: a cycle-finding DFS algorithm on each node individually.
This is a classic White-Gray-Black DFS algorithm. We mark a node 1 on entry and 2 on exit.
If we see a 1 node during our DFS, it must be part of a cycle.

Directed graph of 7 nodes where 0, 1 and 3 form a cycle, nodes 5 and 6 are terminal and nodes 2 and 4 are safe.

Algorithm :

When we visit a node, the only possibilities are:
1. We’ve marked the entire subtree 2 (which must be eventually safe)
2. It has a cycle and we have only marked the members of that cycle 1.
So indeed, the invariant that 1 nodes are always part of a cycle,
and 2 nodes are always eventually safe is maintained.
In order to exit our search quickly when we find a cycle and not mark other nodes erroneously,
we’ll say the result of visiting a node is false if it is eventually safe, otherwise true.
This allows information that we’ve reached a cycle to propagate up the call stack so that we can terminate our search early..

Implementation :

#include <bits/stdc++.h>
using namespace std;
bool dfs(vector<vector<int> >& graph, int src, vector<int>& vis)
{
    // if the node already visited is being revisited => cycle
    if (vis[src] == 1)
        return true;

    if (vis[src] == 2)
        return false;

    vis[src] = 1; // marking visited in current path
    for (auto x : graph[src])
        if (dfs(graph, x, vis))
            return true;
    vis[src] = 2; // backtracking
    return false;
}
// unvisited 0, visited in current path 1, visited by someother path 2
void find_safe_nodes_Util(int n, vector<vector<int> >& graph)
{
    vector<int> vis(n, 0), ans;
    for (int i = 0; i < n; i++)
        // if cycle is not present then the current node is safe
        if (vis[i] != 1 && !dfs(graph, i, vis))
            cout << i << " ";
}
void find_safe_nodes(int n, vector<vector<int> >& edges)
{
    vector<vector<int> > graph(n, vector<int>());
    // create graph with edges
    for (auto edge : edges)
        graph[edge[0]].push_back(edge[1]);

    find_safe_nodes_Util(n, graph);
}
int main()
{
    int n = 7;
    vector<vector<int> > edges = { { 0, 1 }, { 0, 2 }, { 1, 2 }, { 1, 3 }, { 2, 5 }, { 3, 0 }, { 4, 5 } };
    find_safe_nodes(n, edges);
    return 0;
}

Complexity Analysis :

Time Complexity : O(N + E), where N is the number of nodes in the given graph, and E is the total number of edges.
Space Complexity : O(N) in additional space complexity

Comment
Mithlesh Upadhyay Published 18 Nov 2026 · 4 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials