Eventual Safe States using DFS
We will be solving it using DFS traversal. DFS goes in-depth, i.e., traverses all nodes by going ahead, and when there are no further nodes to traverse in the current path, then it backtracks on the same path and traverses other unvisited nodes.
The algorithm steps are as follows:
- We must traverse all components of the graph.
- Make sure to carry two visited arrays in the DFS call. One is a visited array(vis) and the other is a path-visited(pathVis) array. The visited array keeps a track of visited nodes, and the path-visited keeps a track of visited nodes in the current traversal only
- Along with that, we will be carrying an extra array(check) to mark the safe nodes.
- While making a DFS call, at first we will mark the node as visited in both the arrays and then will traverse through its adjacent nodes. Now, there may be either of the three cases.
- Case 1: If the adjacent node is not visited, we will make a new DFS call recursively with that particular node.
- Case 2: If the adjacent node is visited and also on the same path(i.e marked visited in the pathVis array), we will return true, because it means it has a cycle, thereby the pathVis was true. Returning true will mean the end of the function call, as once we have got a cycle, there is no need to check for further adjacent nodes.
- Case 3: If the adjacent node is visited but not on the same path(i.e not marked in the pathVis array), we will continue to the next adjacent node, as it would have been marked as visited in some other path, and not on the current one.
- Finally, if there are no further nodes to visit, we will mark the node as safe in the check array and unmark the current node in the pathVis array and just return false. Then we will backtrack to the previous node with the returned value.
Note: The Point to remember is, while we enter we mark both the pathVis and vis as true, but at the end of traversal to all adjacent nodes, we just make sure to mark the current node safe and unmark the pathVis and still keep the vis marked as true, as it will avoid future extra traversal calls.
The following illustration will be useful in understanding the algorithm:
Below is the implementation of the above approach:
// C++ implementation of the above code
#include <bits/stdc++.h>
using namespace std;
// Function to traverse over the nodes
bool dfs(vector<vector<int> > al, vector<int>& visit,
vector<int>& path, int sr)
{
visit[sr] = 1;
path[sr] = 1;
for (int i : al[sr]) {
if (visit[i] == 0) {
if (dfs(al, visit, path, i) == true)
return true;
}
else if (path[i] == 1)
return true;
}
path[sr] = 0;
return false;
}
// To find safe states
vector<int> eventualSafeNodes(int V,
vector<vector<int> > al)
{
// Your code here
vector<int> visit(V, 0);
vector<int> path(V, 0);
for (int i = 0; i < V; i++) {
if (visit[i] == 0)
dfs(al, visit, path, i);
}
vector<int> res;
for (int i = 0; i < V; i++) {
if (visit[i] == 1 && path[i] == 0)
res.push_back(i);
}
return res;
}
// Driver code
int main()
{
int v = 6;
vector<vector<int> > al(v);
al[5].push_back(0);
al[5].push_back(2);
al[4].push_back(0);
al[2].push_back(3);
al[3].push_back(1);
al[4].push_back(1);
// Function call
vector<int> res = eventualSafeNodes(v, al);
// Output
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
// This code is contributed by prasad264
// Java implementation of the above code
import java.util.*;
public class EvantualSafePlace {
// To find safe states
static ArrayList<Integer>
eventualSafeNodes(int V,
ArrayList<ArrayList<Integer> > al)
{
// Your code here
int[] visit = new int[V];
int[] path = new int[V];
for (int i = 0; i < V; i++) {
if (visit[i] == 0)
dfs(al, visit, path, i);
}
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < V; i++) {
if (visit[i] == 1 && path[i] == 0)
res.add(i);
}
return res;
}
// Function to traverse over the nodes
static boolean dfs(ArrayList<ArrayList<Integer> > al,
int[] visit, int[] path, int sr)
{
visit[sr] = 1;
path[sr] = 1;
for (int i : al.get(sr)) {
if (visit[i] == 0) {
if (dfs(al, visit, path, i) == true)
return true;
}
else if (path[i] == 1)
return true;
}
path[sr] = 0;
return false;
}
// Driver code
public static void main(String[] args)
{
int v = 6;
ArrayList<ArrayList<Integer> > al
= new ArrayList<>(v);
for (int i = 0; i < v; i++) {
al.add(new ArrayList<Integer>());
}
al.get(5).add(0);
al.get(5).add(2);
al.get(4).add(0);
al.get(2).add(3);
al.get(3).add(1);
al.get(4).add(1);
// Function call
ArrayList<Integer> res = eventualSafeNodes(v, al);
// Output
System.out.println(res);
}
}
# Python implementation of the above code
# Function to traverse over the nodes
def dfs(al, visit, path, sr):
visit[sr] = 1
path[sr] = 1
for i in al[sr]:
if visit[i] == 0:
if dfs(al, visit, path, i) == True:
return True
elif path[i] == 1:
return True
path[sr] = 0
return False
# To find safe states
def eventualSafeNodes(V, al):
visit = [0]*V
path = [0]*V
for i in range(V):
if visit[i] == 0:
dfs(al, visit, path, i)
res = []
for i in range(V):
if visit[i] == 1 and path[i] == 0:
res.append(i)
return res
# Driver code
v = 6
al = [[] for _ in range(v)]
al[5].append(0)
al[5].append(2)
al[4].append(0)
al[2].append(3)
al[3].append(1)
al[4].append(1)
# Function call
res = eventualSafeNodes(v, al)
# Output
for i in range(len(res)):
print(res[i], end=" ")
print()
# This code is contributed by prasad264
using System;
using System.Collections.Generic;
public class Program {
public static bool Dfs(List<List<int> > al,
List<int> visit, List<int> path,
int sr)
{
visit[sr] = 1;
path[sr] = 1;
foreach(int i in al[sr])
{
if (visit[i] == 0) {
if (Dfs(al, visit, path, i) == true)
return true;
}
else if (path[i] == 1)
return true;
}
path[sr] = 0;
return false;
}
public static List<int>
EventualSafeNodes(int V, List<List<int> > al)
{
List<int> visit = new List<int>(new int[V]);
List<int> path = new List<int>(new int[V]);
for (int i = 0; i < V; i++) {
if (visit[i] == 0)
Dfs(al, visit, path, i);
}
List<int> res = new List<int>();
for (int i = 0; i < V; i++) {
if (visit[i] == 1 && path[i] == 0)
res.Add(i);
}
return res;
}
public static void Main()
{
int v = 6;
List<List<int> > al = new List<List<int> >();
for (int i = 0; i < v; i++) {
al.Add(new List<int>());
}
al[5].Add(0);
al[5].Add(2);
al[4].Add(0);
al[2].Add(3);
al[3].Add(1);
al[4].Add(1);
// Function call
List<int> res = EventualSafeNodes(v, al);
// Output
foreach(int i in res) { Console.Write(i + " "); }
Console.WriteLine();
}
}
// JavaScript implementation of the above code
// Function to traverse over the nodes
function dfs(al, visit, path, sr) {
visit[sr] = 1;
path[sr] = 1;
for (let i of al[sr]) {
if (visit[i] == 0) {
if (dfs(al, visit, path, i) == true)
return true;
}
else if (path[i] == 1) {
return true;
}
}
path[sr] = 0;
return false;
}
// To find safe states
function eventualSafeNodes(V, al) {
let visit = Array(V).fill(0);
let path = Array(V).fill(0);
for (let i = 0; i < V; i++) {
if (visit[i] == 0) {
dfs(al, visit, path, i);
}
}
let res = [];
for (let i = 0; i < V; i++) {
if (visit[i] == 1 && path[i] == 0) {
res.push(i);
}
}
return res;
}
// Driver code
let v = 6;
let al = Array(v).fill().map(() => []);
al[5].push(0);
al[5].push(2);
al[4].push(0);
al[2].push(3);
al[3].push(1);
al[4].push(1);
// Function call
let res = eventualSafeNodes(v, al);
// Output
console.log(res.join(" "));
Output
0 1 2 3 4 5
Time Complexity: O(V2)
Auxiliary Space: O(V2)
Eventual Safe States
A directed graph of V vertices and E edges is given in the form of an adjacency list adj. Each node of the graph is labeled with a distinct integer in the range 0 to V – 1. A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node, the task is to return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
Examples:
Input: N = 7, E = 7
Example 1
Output: 2, 4, 5, 6
Explanation: The given graph is shown above. Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them. Every path starting at nodes 2, 4, 5, and 6 all leads to either node 5 or 6.Input: N = 4, E = 4
Example-2
Output: 3
Explanation: Node 3 itself is a terminal node and it is a safe node as well. But all the paths from other nodes do not lead to a terminal node. So they are excluded from the answer.