Find eventual safe states

Intuition:

It can be observed that all possible paths starting from a node are going to end at some terminal node unless there exists a cycle and the paths return back to themselves.

Understanding:

Consider the below graph:

It is clear that these types of nodes will never be considered safe:

One is which are occuring in a cycle. Example: Nodes 0, 1 and 3.
Second is which are leading to a cycle. Example: Node 7.

Except these types of nodes, all other nodes will be considered eventually safe.

Hence in order to find the safe nodes, the unsafe nodes can be detected by checking if they exist or point to a cycle. Now, a cycle detection technique is already known to us as discussed in detect cycles in a Directed graph (Using DFS).

Approach:

Initialize three arrays to keep track of visited nodes, nodes in the current traversal path, and nodes identified as safe. Each node starts as unvisited and is considered potentially unsafe until proven otherwise.
Perform a DFS from each node that has not been visited yet. During the DFS traversal, mark the current node as visited and add it to the current path. Assume the current node is unsafe initially.
For each adjacent node of the current node:
- If the adjacent node is unvisited, recursively perform DFS on it.
- If the adjacent node is in the current path, a cycle is detected, making the node unsafe.
If any adjacent node leads to a cycle, the current node remains marked as unsafe.
If no cycles are detected from the current node and its paths, mark the current node as safe. Remove the current node from the path, as the DFS for this node is complete.
After the entire graph is traversed, gather all nodes marked as safe and return the result.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    /* Function to perform DFS traversal 
    while checking for safe nodes */
    bool dfsCheck(int node, vector<int> adj[], 
                  vector<int> &vis, 
                  vector<int> &pathVis, 
                  vector<int> &check) {
                      
        // Mark the node as visited
		vis[node] = 1;
		
		// Add the node to current path
		pathVis[node] = 1;
		
		// Mark the node as potentially unsafe
		check[node] = 0;
		
		
		// Traverse for adjacent nodes
		for (auto it : adj[node]) {
		    
			// When the node is not visited
			if (!vis[it]) {
			    
			    /* Perform DFS recursively and if 
			    a cycle is found, return false */
    			if (dfsCheck(it, adj, vis, pathVis, check)) {
    			        
    			        /* Return true since a 
    			        cycle was detected */
    					return true;
    				}

			}
			
			/* Else if the node has been previously 
			visited in the same path*/
			else if (pathVis[it]) {
				
				/* Return true since a 
		        cycle was detected */
				return true;
			}
		}
		
		/* If the current node neither exist 
		in a cycle nor points to a cycle, 
		it can be marked as a safe node */
		check[node] = 1;
		
		// Remove the node from the current path
		pathVis[node] = 0;
		
		// Return false since no cycle was found
		return false;
	}
    
public:

	/* Function to get the
	eventually safe nodes */
	vector<int> eventualSafeNodes(int V, 
	                vector<int> adj[]) {
	   
	    // Visited array
	    vector<int> vis(V, false);
	    
	    // Path Visited array
	    vector<int> pathVis(V, false);
	    
	    // To keep a check of safe nodes
	    vector<int> check(V, false);
	    
	    /* Traverse the graph and 
	    check for safe nodes */
		for (int i = 0; i < V; i++) {
			if (!vis[i]) {
			    
			    // Start DFS traversal
				dfsCheck(i, adj, vis, pathVis, check);
			}
		}
		
		// To store the result
		vector<int> ans;
		
		// Add the safe nodes to the result
		for (int i = 0; i < V; i++) {
			if (check[i] == 1) 
			    ans.push_back(i);
		}
		
		// Return the result
		return ans;
	}
};

int main() {
    
    int V = 7;
    vector<int> adj[V] = {
         {1,2},
         {2,3},
         {5},
         {0},
         {5},
         {},
         {}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the eventually 
    safe nodes in the given graph */
    vector<int> ans = sol.eventualSafeNodes(V, adj);
    
    // Output
    cout << "The eventually safe nodes in the graph are:\n";
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    
    /* Function to perform DFS traversal 
    while checking for safe nodes */
    private boolean dfsCheck(int node, int[][] adj, 
                             boolean[] vis, 
                             boolean[] pathVis, 
                             boolean[] check) {
                                 
        // Mark the node as visited
        vis[node] = true;
        
        // Add the node to current path
        pathVis[node] = true;
        
        // Mark the node as potentially unsafe
        check[node] = false;
        
        // Traverse for adjacent nodes
        for (int it : adj[node]) {
            
            // When the node is not visited
            if (!vis[it]) {
                
                /* Perform DFS recursively and if 
                a cycle is found, return false */
                if (dfsCheck(it, adj, vis, pathVis, check)) {
                    
                    /* Return true since a 
                    cycle was detected */
                    return true;
                }

            }
            
            /* Else if the node has been previously 
            visited in the same path*/
            else if (pathVis[it]) {
                
                /* Return true since a 
                cycle was detected */
                return true;
            }
        }
        
        /* If the current node neither exist 
        in a cycle nor points to a cycle, 
        it can be marked as a safe node */
        check[node] = true;
        
        // Remove the node from the current path
        pathVis[node] = false;
        
        // Return false since no cycle was found
        return false;
    }
    
    // Function to get the eventually safe nodes
    public int[] eventualSafeNodes(int V, int[][] adj) {
        
        // Visited array
        boolean[] vis = new boolean[V];
        
        // Path Visited array
        boolean[] pathVis = new boolean[V];
        
        // To keep a check of safe nodes
        boolean[] check = new boolean[V];
        
        /* Traverse the graph and 
        check for safe nodes */
        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                
                // Start DFS traversal
                dfsCheck(i, adj, vis, pathVis, check);
            }
        }
        
        // To store the result
        List<Integer> temp = new ArrayList<>();
        
        // Add the safe nodes to the result
        for (int i = 0; i < V; i++) {
            if (check[i]) 
                temp.add(i);
        }
        
        // Convert List to array
        int[] ans = new int[temp.size()];
        for (int i = 0; i < temp.size(); i++) {
            ans[i] = temp.get(i);
        }
        
        // Return the result
        return ans;
    }
    
    public static void main(String[] args) {
        int V = 7;
        int[][] adj = {
            {1, 2},
            {2, 3},
            {5},
            {0},
            {5},
            {},
            {}
        };
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to get the eventually 
        safe nodes in the given graph */
        int[] ans = sol.eventualSafeNodes(V, adj);
        
        // Output
        System.out.println("The eventually safe nodes in the graph are:");
        for (int node : ans) {
            System.out.print(node + " ");
        }
    }
}
from typing import List

class Solution:
    
    # Function to perform DFS traversal 
    # while checking for safe nodes
    def dfsCheck(self, node: int, adj: List[List[int]], 
                 vis: List[bool], 
                 pathVis: List[bool], 
                 check: List[bool]) -> bool:
                      
        # Mark the node as visited
        vis[node] = True
        
        # Add the node to current path
        pathVis[node] = True
        
        # Mark the node as potentially unsafe
        check[node] = False
        
        # Traverse for adjacent nodes
        for it in adj[node]:
            
            # When the node is not visited
            if not vis[it]:
                
                # Perform DFS recursively and if 
                # a cycle is found, return false
                if self.dfsCheck(it, adj, vis, pathVis, check):
                    
                    # Return true since a 
                    # cycle was detected
                    return True

            # Else if the node has been previously 
            # visited in the same path
            elif pathVis[it]:
                
                # Return true since a 
                # cycle was detected
                return True
        
        # If the current node neither exist 
        # in a cycle nor points to a cycle, 
        # it can be marked as a safe node
        check[node] = True
        
        # Remove the node from the current path
        pathVis[node] = False
        
        # Return false since no cycle was found
        return False

    # Function to get the eventually safe nodes
    def eventualSafeNodes(self, V, adj):
        
        # Visited array
        vis = [False] * V
        
        # Path Visited array
        pathVis = [False] * V
        
        # To keep a check of safe nodes
        check = [False] * V
        
        # Traverse the graph and 
        # check for safe nodes
        for i in range(V):
            if not vis[i]:
                
                # Start DFS traversal
                self.dfsCheck(i, adj, vis, pathVis, check)
        
        # To store the result
        ans = []
        
        # Add the safe nodes to the result
        for i in range(V):
            if check[i]:
                ans.append(i)
        
        # Return the result
        return ans

# Main function
if __name__ == "__main__":
    
    V = 7
    adj = [
         [1,2],
         [2,3],
         [5],
         [0],
         [5],
         [],
         []
    ]
    
    # Creating an instance of 
    # Solution class
    sol = Solution() 
    
    # Function call to get the eventually 
    # safe nodes in the given graph
    ans = sol.eventualSafeNodes(V, adj)
    
    # Output
    print("The eventually safe nodes in the graph are:")
    for node in ans:
        print(node, end=" ")
class Solution {
    // Function to perform DFS traversal 
    // while checking for safe nodes
    dfsCheck(node, adj, vis, pathVis, check) {
        // Mark the node as visited
        vis[node] = true;
        
        // Add the node to current path
        pathVis[node] = true;
        
        // Mark the node as potentially unsafe
        check[node] = false;
        
        // Traverse for adjacent nodes
        for (let it of adj[node]) {
            
            // When the node is not visited
            if (!vis[it]) {
                
                // Perform DFS recursively and if 
                // a cycle is found, return false
                if (this.dfsCheck(it, adj, vis, pathVis, check)) {
                    
                    // Return true since a 
                    // cycle was detected
                    return true;
                }

            }
            
            // Else if the node has been previously 
            // visited in the same path
            else if (pathVis[it]) {
                
                // Return true since a 
                // cycle was detected
                return true;
            }
        }
        
        // If the current node neither exist 
        // in a cycle nor points to a cycle, 
        // it can be marked as a safe node
        check[node] = true;
        
        // Remove the node from the current path
        pathVis[node] = false;
        
        // Return false since no cycle was found
        return false;
    }

    // Function to get the eventually safe nodes
    eventualSafeNodes(V, adj) {
        
        // Visited array
        let vis = new Array(V).fill(false);
        
        // Path Visited array
        let pathVis = new Array(V).fill(false);
        
        // To keep a check of safe nodes
        let check = new Array(V).fill(false);
        
        // Traverse the graph and 
        // check for safe nodes
        for (let i = 0; i < V; i++) {
            if (!vis[i]) {
                
                // Start DFS traversal
                this.dfsCheck(i, adj, vis, pathVis, check);
            }
        }
        
        // To store the result
        let ans = [];
        
        // Add the safe nodes to the result
        for (let i = 0; i < V; i++) {
            if (check[i]) 
                ans.push(i);
        }
        
        // Return the result
        return ans;
    }
}

// Main function
let V = 7;
let adj = [
     [1,2],
     [2,3],
     [5],
     [0],
     [5],
     [],
     []
];

// Creating an instance of 
// Solution class
let sol = new Solution(); 

// Function call to get the eventually 
// safe nodes in the given graph
let ans = sol.eventualSafeNodes(V, adj);

// Output
console.log("The eventually safe nodes in the graph are:");
for (let i = 0; i < ans.length; i++) {
    console.log(ans[i] + " ");
}

Complexity Analysis:

Time Complexity: O(V+E) (where V and E represents the number of nodes and edges in the given graph)
DFS traversal takes O(V+E) time and adding the safe nodes to the result takes O(V) time.

Space Complexity: O(V)
The visited, path visited, and check array take O(V) space each and the recursion stack space will be O(V) in the worst case.

Intuition:

It can be observed that all possible paths starting from a node are going to end at some terminal node unless there exists a cycle and the paths return back to themselves.

Understanding:

Consider the below graph:

It is clear that these types of nodes will never be considered safe:

One is which is occurring in a cycle. Example: Nodes 0, 1, and 3.
Second is which is leading to a cycle. Example: Node 7.

Except these types of nodes, all other nodes will be considered eventually safe.

Hence in order to find the safe nodes, the unsafe nodes can be detected by checking if they exist or point to a cycle. Now, to solve this using BFS traversal technique, the topological sorting (Kahn's Algorithm) can be used. The topological sort algorithm will automatically exclude the nodes which are either forming a cycle or connected to a cycle.

Transforming the graph:

The node with outdegree 0 is considered as terminal node but the topological sort algorithm deals with the indegrees of the nodes. So, to use the topological sort algorithm, we will reverse every edge of the graph.

Approach:

Reverse the edges of the graph reversing the graph.
Find the topological sort of the reversed graph which will exclude automatically the unsafe nodes.
Sort the ordering returned by topological sort to obtain the eventually safe nodes in a sorted fashion.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    /* Function to return the topological
     sorting of given graph */
    vector<int> topoSort(int V, vector<int> adj[]) {
	    
        // To store the In-degrees of nodes
	    vector<int> inDegree(V, 0);
	    
	    // Update the in-degrees of nodes
		for (int i = 0; i < V; i++) {
		    
			for(auto it : adj[i]) {
			    // Update the in-degree
			    inDegree[it]++;
			}
		}

        
        // To store the result
        vector<int> ans;
	    
	    // Queue to facilitate BFS
	    queue<int> q;
	    
	    // Add the nodes with no in-degree to queue
	    for(int i=0; i<V; i++) {
	        if(inDegree[i] == 0) q.push(i);
	    }
	    
	    // Until the queue is empty
	    while(!q.empty()) {
	        
	        // Get the node
	        int node = q.front();
	        
	        // Add it to the answer
	        ans.push_back(node);
	        q.pop();
	        
	        // Traverse the neighbours
	        for(auto it : adj[node]) {
	            
	            // Decrement the in-degree
	            inDegree[it]--;
	            
	            /* Add the node to queue if 
	            its in-degree becomes zero */
	            if(inDegree[it] == 0) q.push(it);
	        }
	    }
	    
	    // Return the result
	    return ans;
    }
    
public:

	/* Function to get the
	eventually safe nodes */
	vector<int> eventualSafeNodes(int V, 
	                vector<int> adj[]) {
	    
	    // To store the reverse graph
	    vector<int> adjRev[V];
	    
	    // Reversing the edges
	    for (int i = 0; i < V; i++) {
		    
			// i -> it, it-> i
			for (auto it : adj[i]) {
			    
			    // Add the edge to reversed graph
				adjRev[it].push_back(i);
			}
		}
		
	    /* Return the topological 
	    sort of the given graph */
	    vector<int> result = topoSort(V, adjRev);
	    
	    // Sort the result
	    sort(result.begin(), result.end());
	    
	    // Return the result
	    return result;
	}
};

int main() {
    
    int V = 7;
    vector<int> adj[V] = {
         {1,2},
         {2,3},
         {5},
         {0},
         {5},
         {},
         {}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the eventually 
    safe nodes in the given graph */
    vector<int> ans = sol.eventualSafeNodes(V, adj);
    
    // Output
    cout << "The eventually safe nodes in the graph are:\n";
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    
    /* Function to return the topological
     sorting of given graph */
    private int[] topoSort(int V, 
            List<Integer>[] adj) {
	    
        // To store the In-degrees of nodes
	    int[] inDegree = new int[V];
	    
	    // Update the in-degrees of nodes
		for (int i = 0; i < V; i++) {
		    
			for(int it : adj[i]) {
			    // Update the in-degree
			    inDegree[it]++;
			}
		}

        // To store the result
        int[] ans = new int[V];
        int idx = 0;
	    
	    // Queue to facilitate BFS
	    Queue<Integer> q = new LinkedList<>();
	    
	    // Add the nodes with no in-degree to queue
	    for(int i = 0; i < V; i++) {
	        if(inDegree[i] == 0) q.add(i);
	    }
	    
	    // Until the queue is empty
	    while(!q.isEmpty()) {
	        
	        // Get the node
	        int node = q.poll();
	        
	        // Add it to the answer
	        ans[idx++] = node;
	        
	        // Traverse the neighbours
	        for(int it : adj[node]) {
	            
	            // Decrement the in-degree
	            inDegree[it]--;
	            
	            /* Add the node to queue if 
	            its in-degree becomes zero */
	            if(inDegree[it] == 0) q.add(it);
	        }
	    }
	    
	    // Return the result
	    return Arrays.copyOfRange(ans, 0, idx);
    }
    
    /* Function to get the
	eventually safe nodes */
    public int[] eventualSafeNodes(int V, 
                            int[][] adj) {
	    
	    // To store the reverse graph
	    ArrayList<Integer>[] adjRev = new ArrayList[V];
	    for (int i = 0; i < V; i++) 
	        adjRev[i] = new ArrayList<>();
	    
	    // Reversing the edges
	    for (int i = 0; i < V; i++) {
		    
			// i -> it, it-> i
			for (int it : adj[i]) {
			    
			    // Add the edge to reversed graph
				adjRev[it].add(i);
			}
		}
		
	    /* Return the topological 
	    sort of the given graph */
	    int[] result = topoSort(V, adjRev);
	    
	    // Sort the result
	    Arrays.sort(result);
	    
	    // Return the result
	    return result;
	}

    public static void main(String[] args) {
        int V = 7;
        int[][] adj = {
            {1, 2},
            {2, 3},
            {5},
            {0},
            {5},
            {},
            {}
        };
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to get the eventually 
        safe nodes in the given graph */
        int[] ans = sol.eventualSafeNodes(V, adj);
        
        // Output
        System.out.println("The eventually safe nodes in the graph are:");
        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}
from collections import deque

class Solution:

    # Function to return the topological
    # sorting of given graph
    def topoSort(self, V, adj):
        
        # To store the In-degrees of nodes
        inDegree = [0] * V
        
        # Update the in-degrees of nodes
        for i in range(V):
            
            for it in adj[i]:
                # Update the in-degree
                inDegree[it] += 1

        # To store the result
        ans = []
        
        # Queue to facilitate BFS
        q = deque()
        
        # Add the nodes with no in-degree to queue
        for i in range(V):
            if inDegree[i] == 0:
                q.append(i)
        
        # Until the queue is empty
        while q:
            
            # Get the node
            node = q.popleft()
            
            # Add it to the answer
            ans.append(node)
            
            # Traverse the neighbours
            for it in adj[node]:
                
                # Decrement the in-degree
                inDegree[it] -= 1
                
                # Add the node to queue if 
                # its in-degree becomes zero
                if inDegree[it] == 0:
                    q.append(it)
        
        # Return the result
        return ans

    # Function to get the
    # eventually safe nodes
    def eventualSafeNodes(self, V, adj):
        
        # To store the reverse graph
        adjRev = [[] for _ in range(V)]
        
        # Reversing the edges
        for i in range(V):
            
            # i -> it, it-> i
            for it in adj[i]:
                
                # Add the edge to reversed graph
                adjRev[it].append(i)
        
        # Return the topological 
        # sort of the given graph
        result = self.topoSort(V, adjRev)
        
        # Sort the result
        result.sort()
        
        # Return the result
        return result

# Example usage
V = 7
adj = [
    [1, 2],
    [2, 3],
    [5],
    [0],
    [5],
    [],
    []
]

sol = Solution()
ans = sol.eventualSafeNodes(V, adj)

# Output
print("The eventually safe nodes in the graph are:")
print(" ".join(map(str, ans)))
class Solution {

    /* Function to return the topological
     sorting of given graph */
    topoSort(V, adj) {
        
        // To store the In-degrees of nodes
        let inDegree = new Array(V).fill(0);
        
        // Update the in-degrees of nodes
        for (let i = 0; i < V; i++) {
            
            for(let it of adj[i]) {
                // Update the in-degree
                inDegree[it]++;
            }
        }

        // To store the result
        let ans = [];
        
        // Queue to facilitate BFS
        let q = [];
        
        // Add the nodes with no in-degree to queue
        for(let i = 0; i < V; i++) {
            if(inDegree[i] == 0) q.push(i);
        }
        
        // Until the queue is empty
        while(q.length > 0) {
            
            // Get the node
            let node = q.shift();
            
            // Add it to the answer
            ans.push(node);
            
            // Traverse the neighbours
            for(let it of adj[node]) {
                
                // Decrement the in-degree
                inDegree[it]--;
                
                /* Add the node to queue if 
                its in-degree becomes zero */
                if(inDegree[it] == 0) q.push(it);
            }
        }
        
        // Return the result
        return ans;
    }
    
    /* Function to get the
    eventually safe nodes */
    eventualSafeNodes(V, adj) {
        
        // To store the reverse graph
        let adjRev = new Array(V).fill().map(() => []);
        
        // Reversing the edges
        for (let i = 0; i < V; i++) {
            
            // i -> it, it-> i
            for (let it of adj[i]) {
                
                // Add the edge to reversed graph
                adjRev[it].push(i);
            }
        }
        
        /* Return the topological 
        sort of the given graph */
        let result = this.topoSort(V, adjRev);
        
        // Sort the result
        result.sort((a, b) => a - b);
        
        // Return the result
        return result;
    }
}

// Example usage
const V = 7;
const adj = [
    [1, 2],
    [2, 3],
    [5],
    [0],
    [5],
    [],
    []
];

const sol = new Solution();
const ans = sol.eventualSafeNodes(V, adj);

// Output
console.log("The eventually safe nodes in the graph are:");
console.log(ans.join(" "));

Complexity Analysis:

Time Complexity: O(V+E) + O(V*logV) (where V and E represents the number of nodes and edges in the given graph)

Reversing the graph takes O(E) time.
Finding topological sort using Kahn's algorithm takes O(V+E) time.
Sorting the nodes takes O(N*logN) time (where N is the number of safe nodes, which can go up to V in worst-case).

Space Complexity: O(V+E)

Storing the reversed graph takes O(E) space.
Topological sorting algorithm uses extra O(V) space because of in-degrees array and queue data structure.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Understanding:

Approach:

Solution:

Complexity Analysis:

Intuition:

Understanding:

Transforming the graph:

Approach:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code