Let's understand with the following example:

There’s a cycle: 0 → 1 → 3 → 0.
Node 7 connects into this cycle, so it is unsafe.
Node 2, though connected to the cycle, has an outgoing edge leading to terminal node 5. So it is safe.
Nodes 4, 5, and 6 are also safe.

So, the idea is to detect cycles and mark nodes involved in or leading into those cycles as unsafe. All other nodes are safe.

We’ll use cycle detection using DFS to identify unsafe nodes, and all others will be added to the list of safe nodes.

Note: Any node involved in a cycle, or with a path leading into a cycle, is not a safe node.

We'll use DFS traversal to detect cycles in the directed graph. DFS goes deep along one path and then backtracks once it hits the end.

Algorithm Steps:

Traverse each component of the graph.
Maintain:
- vis[] – to mark if a node has ever been visited.
- pathVis[] – to mark if a node is currently in the DFS path.
- check[] – to mark whether a node is safe.
During DFS:
- Mark the node as visited in both vis and pathVis.
- For every adjacent node:
  - Case 1: If unvisited, make a recursive DFS call.
  - Case 2: If visited and also marked in pathVis, it's a cycle → return true.
  - Case 3: If visited but not in pathVis, continue to next.
If no cycle is found from the current node, mark it as safe in check[], unmark pathVis, and return false.

Key Point: Keep vis[] true even after backtracking to avoid re-processing nodes. Only reset pathVis[] during backtrack.

Code