POTD Solutions | 18 Oct’ 23 | Eventual Safe States
Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Graph Data Structure but will also help you build up problem-solving skills.
POTD 18 October: 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 labelled 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.
You have to return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
Example 1:
Input:
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 lead to either node 5 or 6.
Example 2:
Input:
Output: 3
Explanation: Only node 3 is a terminal node, and every path starting at node 3 leads to node 3.
Eventual Safe States using DFS
We can use DFS approach, 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.
Step-by-step algorithm:
- Implement a dfs() function to detect cycles in the graph.
- Create a eventualSafeNodes() function to find safe nodes.
- In eventualSafeNodes() mark nodes in the cycle using DFS.
- Add nodes not in any cycle to the safeNodes array.
- Return the safeNodes list as the result.
Below is the implementation of above approach:
C++
// Back-end complete function Template for C++ class Solution { public : // Function to perform depth-first search to check if // there is a cycle and mark the nodes present in the // cycle bool dfs( int u, vector< int > adj[], vector< bool >& is_visited, vector< bool >& in_stack, vector< bool >& nodes_present_in_cycle) { is_visited[u] = true ; in_stack[u] = true ; // Iterate over the adjacent nodes for ( auto v : adj[u]) { if (!is_visited[v]) { // Recursively call dfs on unvisited nodes bool is_cycle_present = dfs(v, adj, is_visited, in_stack, nodes_present_in_cycle); // If cycle is present, mark nodes in the // cycle and return true if (is_cycle_present) { return nodes_present_in_cycle[u] = true ; } } else if (is_visited[v] && in_stack[v]) { // If the node is visited and in the // recursion stack, cycle is present return nodes_present_in_cycle[u] = true ; } } // Mark the node as not in recursion stack and // return false in_stack[u] = false ; return false ; } // Function to find the eventual safe nodes vector< int > eventualSafeNodes( int V, vector< int > adj[]) { vector< int > safeNodes; vector< bool > is_visited(V, false ); vector< bool > in_stack(V, false ); vector< bool > nodes_present_in_cycle(V, false ); // Iterate over all the nodes for ( int i = 0; i < V; i++) { if (!is_visited[i]) { // Call dfs for unvisited nodes dfs(i, adj, is_visited, in_stack, nodes_present_in_cycle); } } // Add nodes that are not present in any cycle to // the safeNodes list for ( int i = 0; i < V; i++) { if (!nodes_present_in_cycle[i]) { safeNodes.push_back(i); } } // Return the list of safe nodes return safeNodes; } }; |
Java
// Back-end complete function Template for Java class Solution { // Depth First Search function to check for cycles in // the graph and identify nodes present in cycles boolean dfs( int u, List<List<Integer> > adj, boolean [] is_visited, boolean [] in_stack, boolean [] nodes_present_in_cycle) { is_visited[u] = true ; in_stack[u] = true ; // check each adjacent node for ( int v : adj.get(u)) { if (!is_visited[v]) { // recursively call dfs on unvisited nodes boolean is_cycle_present = dfs(v, adj, is_visited, in_stack, nodes_present_in_cycle); if (is_cycle_present) { // if a cycle is present, mark the // current node and return true return nodes_present_in_cycle[u] = true ; } } else if (is_visited[v] && in_stack[v]) { // if an adjacent node is already visited // and is in the current path, mark the // current node and return true return nodes_present_in_cycle[u] = true ; } } // mark the current node as not in the current path // and return false in_stack[u] = false ; return false ; } // Function to find the nodes that are eventually safe List<Integer> eventualSafeNodes( int V, List<List<Integer> > adj) { List<Integer> safeNodes = new ArrayList<>(); boolean [] is_visited = new boolean [V]; boolean [] in_stack = new boolean [V]; boolean [] nodes_present_in_cycle = new boolean [V]; // iterate over each node in the graph and perform // dfs to check for cycles for ( int i = 0 ; i < V; i++) { if (!is_visited[i]) { dfs(i, adj, is_visited, in_stack, nodes_present_in_cycle); } } // add nodes that are not present in any cycle to // the safeNodes list for ( int i = 0 ; i < V; i++) { if (!nodes_present_in_cycle[i]) { safeNodes.add(i); } } // return the list of safe nodes return safeNodes; } }; |
Python3
# Back-end complete function Template for Python 3 from typing import List import sys sys.setrecursionlimit( 10 * * 8 ) # Depth First Search to check if a cycle is present and mark the nodes present in the cycle def dfs(u, adj, is_visited, in_stack, nodes_present_in_cycle): is_visited[u] = True in_stack[u] = True # Explore all the adjacent nodes for v in adj[u]: if is_visited[v] = = False : # Recursive call to check if there is a cycle is_cycle_present = dfs( v, adj, is_visited, in_stack, nodes_present_in_cycle) if is_cycle_present = = True : # Mark the current node as present in the cycle and return True nodes_present_in_cycle[u] = True return True # If an adjacent node is visited and is in the current recursion stack, a cycle is present elif is_visited[v] = = True and in_stack[v] = = True : nodes_present_in_cycle[u] = True return True # Mark the current node as not in recursion stack in_stack[u] = False return False class Solution: def eventualSafeNodes( self , V: int , adj: List [ List [ int ]]) - > List [ int ]: safeNodes = [] is_visited = [ False ] * V in_stack = [ False ] * V nodes_present_in_cycle = [ False ] * V # Traverse each node and perform a DFS for i in range (V): if is_visited[i] = = False : dfs(i, adj, is_visited, in_stack, nodes_present_in_cycle) # Add the nodes that are not present in any cycle to the safeNodes list for i in range (V): if nodes_present_in_cycle[i] = = False : safeNodes.append(i) return safeNodes |
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges
Auxiliary Space: O(V)
Contact Us