Eventual Safe States using BFS
- Reverse the adjacency list so, that we can do the topological sort on the basis of outdegree instead of indegree.
- Compute the indegree for each of the vertex.
- Add all the vertices with indegree zero in the queue.
- Do bfs, remove the vertex from the queue and
- Store the front of the queue.
- Decrement the indegree by one for all its neighboring nodes.
- if the indegree is reduced to zero, add them to the queue.
- Repeat step-4 until queue is empty.
- Sort the answer and return it.
Below is the implementation of the above approach:
// C++ implementation of the above code
#include <bits/stdc++.h>
using namespace std;
// To find safe states
vector<int> eventualSafeNodes(int V,
vector<vector<int> > al)
{
// Your code here
vector<int> adjRev[V];
int indegree[V] = {0};
for (int i = 0; i < V; i++) {
for(auto it: al[i]){
//reverse the adjacency list
adjRev[it].push_back(i);
//compute the indegree for every vertex
indegree[i]++;
}
}
queue<int> q;
vector<int> safeNodes;
//adding the vertices with indegree zero in the queue
for(int i=0;i<V;i++){
if(indegree[i]==0){
q.push(i);
}
}
while(!q.empty()){
int node = q.front();
q.pop();
//store the answer
safeNodes.push_back(node);
for(auto nbr: adjRev[node]){
//decrement the indegree of all the neighbouring nodes of the node
indegree[nbr]--;
//if the indegree of any neighbouring node become zero,
//put it in the queue.
if(indegree[nbr]==0){
q.push(nbr);
}
}
}
// sort the answer
sort(safeNodes.begin(), safeNodes.end());
//returning the answer
return safeNodes;
}
// 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 525tamannacse1
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
public static List<Integer> eventualSafeNodes(int V, List<List<Integer>> al) {
List<List<Integer>> adjRev = new ArrayList<>();
for (int i = 0; i < V; i++) {
adjRev.add(new ArrayList<>());
}
int indegree[] = new int[V];
for (int i = 0; i < V; i++) {
for (int it : al.get(i)) {
adjRev.get(it).add(i);
indegree[i]++;
}
}
Queue<Integer> q = new LinkedList<>();
List<Integer> safeNodes = new ArrayList<>();
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
q.add(i);
}
}
while (!q.isEmpty()) {
int node = q.peek();
q.remove();
safeNodes.add(node);
for (int it : adjRev.get(node)) {
indegree[it]--;
if (indegree[it] == 0) q.add(it);
}
}
Collections.sort(safeNodes);
return safeNodes;
}
public static void main(String[] args) {
int V = 6;
List<List<Integer>> al = new ArrayList<>();
for (int i = 0; i < V; i++) {
al.add(new ArrayList<>());
}
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);
List<Integer> res = eventualSafeNodes(V,al);
for (int i=0;i<res.size();i++) {
System.out.print(res.get(i) + " ");
}
System.out.println("");
}
}
from collections import deque
def eventual_safe_nodes(V, al):
adj_rev = [[] for _ in range(V)]
indegree = [0] * V
for i in range(V):
for j in al[i]:
adj_rev[j].append(i)
indegree[i] += 1
q = deque()
safe_nodes = []
for i in range(V):
if indegree[i] == 0:
q.append(i)
while q:
node = q.popleft()
safe_nodes.append(node)
for nbr in adj_rev[node]:
indegree[nbr] -= 1
if indegree[nbr] == 0:
q.append(nbr)
safe_nodes.sort()
return safe_nodes
# Driver code
v = 6
al = [[] for _ in range(v)]
al[5].extend([0, 2])
al[4].extend([0, 1])
al[2].append(3)
al[3].append(1)
al[4].append(1)
# Function call
res = eventual_safe_nodes(v, al)
# Output
for i in res:
print(i, end=" ")
// C# Code
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
public static List<int> EventualSafeNodes(int V, List<List<int>> al)
{
// Create a reversed adjacency list
List<List<int>> adjRev = new List<List<int>>();
for (int i = 0; i < V; i++)
{
adjRev.Add(new List<int>());
}
int[] indegree = new int[V];
// Populate the reversed adjacency list and calculate indegrees
for (int i = 0; i < V; i++)
{
foreach (int it in al[i])
{
adjRev[it].Add(i);
indegree[i]++;
}
}
Queue<int> q = new Queue<int>();
List<int> safeNodes = new List<int>();
// Add nodes with zero indegree to the queue
for (int i = 0; i < V; i++)
{
if (indegree[i] == 0)
{
q.Enqueue(i);
}
}
// Process nodes and reduce indegrees
while (q.Count > 0)
{
int node = q.Peek();
q.Dequeue();
safeNodes.Add(node);
foreach (int it in adjRev[node])
{
indegree[it]--;
if (indegree[it] == 0)
{
q.Enqueue(it);
}
}
}
// Sort the result and return
safeNodes.Sort();
return safeNodes;
}
public static void Main(string[] args)
{
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);
List<int> res = EventualSafeNodes(V, al);
for (int i = 0; i < res.Count; i++)
{
Console.Write(res[i] + " ");
}
Console.WriteLine("");
}
}
// This code is contributed by guptapratik
function eventualSafeNodes(V, al) {
const adjRev = Array.from({ length: V }, () => []);
const indegree = new Array(V).fill(0);
// Initialize adjacency list and indegree array
for (let i = 0; i < V; i++) {
for (const it of al[i]) {
// Reverse the adjacency list
adjRev[it].push(i);
// Compute the indegree for every vertex
indegree[i]++;
}
}
const q = [];
const safeNodes = [];
// Adding the vertices with indegree zero to the queue
for (let i = 0; i < V; i++) {
if (indegree[i] === 0) {
q.push(i);
}
}
while (q.length > 0) {
const node = q.shift();
// Store the answer
safeNodes.push(node);
for (const nbr of adjRev[node]) {
// Decrement the indegree of all neighboring nodes of the node
indegree[nbr]--;
// If the indegree of any neighboring node becomes zero, put it in the queue.
if (indegree[nbr] === 0) {
q.push(nbr);
}
}
}
// Sort the answer
safeNodes.sort((a, b) => a - b);
return safeNodes;
}
const V = 6;
const al = [
[1, 2],
[2],
[3],
[4],
[5],
[]
];
// Function call
const res = eventualSafeNodes(V, al);
// Output
console.log(res.join(" "));
Output
0 1 2 3 4 5
Time Complexity: O(V+E + VLogV), The outer for loop will be executed V number of times and the inner for loop will be executed E number of times VlogV for sorting.
Auxiliary Space: O(V + V) = O(V), The reverse adjacency list requires the O(V) space and the queue also needs to store all the vertices of the graph. So the space required in total is O(V).
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.