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.

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