grid47 Exploring patterns and algorithms
Aug 18, 2024
7 min read
Solution to LeetCode 802: Find Eventual Safe States Problem
You are given a directed graph where each node represents a point, and edges represent possible transitions between nodes. A node is considered terminal if it has no outgoing edges. A node is deemed safe if every path starting from it leads either to a terminal node or another safe node. Your task is to identify all the safe nodes in the graph and return them in ascending order.
Problem
Approach
Steps
Complexity
Input: The input consists of a graph represented as a 2D array, where each node's adjacency list is provided, followed by the conditions of the graph's nodes.
• Explanation: In this graph, nodes 5 and 6 are terminal nodes because they have no outgoing edges. Nodes 2, 4, 5, and 6 are safe since all paths starting from these nodes lead either to a terminal node or another safe node.
• Explanation: In this case, node 4 is the only terminal node, and it is safe. The paths starting at node 4 always lead to itself, making it a safe node.
Approach: To solve this problem, we can use a depth-first search (DFS) approach to explore each node and determine if it is safe based on its outgoing edges and the nodes it leads to.
Observations:
• Safe nodes can be identified by ensuring all paths from them eventually lead to terminal nodes or other safe nodes.
• We will perform DFS from each node, tracking its status as either visiting, visited, or safe. Nodes that are part of cycles or lead to unsafe paths will not be marked as safe.
Steps:
• For each node in the graph, perform a depth-first search (DFS) to check if it eventually reaches a terminal node or a safe node.
• During DFS, track the state of each node (unvisited, visiting, or safe) to handle cycles correctly.
• After the DFS traversal, collect all nodes marked as safe and return them in ascending order.
Empty Inputs:
• If the graph has no nodes, there are no safe nodes to return.
Large Inputs:
• For large inputs, ensure the DFS algorithm is optimized to handle up to 10^4 nodes efficiently.
Special Values:
• If the graph contains self-loops, treat them carefully by marking the node as unsafe if it leads to itself in a cycle.
Constraints:
• Ensure that the solution is efficient given the graph constraints, particularly the number of nodes and edges.
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
vector<int> res;
int n = graph.size();
if(n ==0) return res;
vector<int> vis(n, 0);
for(int i =0; i < n; i++)
if(dfs(graph, i, vis)) res.push_back(i);
return res;
}
intdfs(vector<vector<int>>& graph, int cur, vector<int>&vis) {
if(vis[cur] !=0) return vis[cur] ==2;
vis[cur] =1;
for(autonxt: graph[cur])
if(!dfs(graph, nxt, vis)) returnfalse;
vis[cur] =2;
returntrue;
}
This is the function signature that defines the main function, `eventualSafeNodes`, which takes a graph (a vector of vectors of integers) as input and returns a vector of integers representing the safe nodes.
2 : Variable Declaration
vector<int> res;
A vector `res` is declared to store the eventual safe nodes that will be found during the DFS traversal.
3 : Variable Declaration
int n = graph.size();
The variable `n` is initialized to store the size of the graph (i.e., the number of nodes).
4 : Condition
if(n ==0) return res;
If the graph is empty (n == 0), an empty vector `res` is returned as there are no nodes to process.
5 : Variable Initialization
vector<int> vis(n, 0);
A `vis` vector is initialized with zeroes, where each element represents the visitation state of a node (0 = not visited, 1 = visiting, 2 = visited).
6 : Loop
for(int i =0; i < n; i++)
A for loop is used to iterate over all the nodes in the graph, starting from node 0 to node n-1.
7 : Conditional
if(dfs(graph, i, vis)) res.push_back(i);
For each node, the DFS function is called to check if it's an eventual safe node. If the node is safe (DFS returns true), it is added to the result vector `res`.
8 : Return Statement
return res;
The function returns the vector `res`, which contains all the safe nodes found during the DFS traversal.
9 : Function
intdfs(vector<vector<int>>& graph, int cur, vector<int>&vis) {
This is the helper function `dfs` that performs depth-first search to explore the graph from a given node `cur`.
10 : Condition
if(vis[cur] !=0) return vis[cur] ==2;
If the node `cur` has already been visited (its state is not 0), the function returns whether the node is safe (state 2 means safe).
11 : Mark Node as Visiting
vis[cur] =1;
The node `cur` is marked as visiting (state 1) to indicate that it's being explored.
12 : Loop
for(autonxt: graph[cur])
The function iterates over all the neighboring nodes (`nxt`) of the current node `cur`.
13 : Conditional
if(!dfs(graph, nxt, vis)) returnfalse;
For each neighboring node `nxt`, the DFS function is called recursively. If any neighbor leads to a cycle (DFS returns false), the current node is not safe, and the function returns false.
14 : Mark Node as Safe
vis[cur] =2;
Once all the neighbors have been processed and no cycle is detected, the current node `cur` is marked as safe (state 2).
15 : Return Statement
returntrue;
The function returns true, indicating that the current node `cur` is safe.
Best Case: O(n + e), where n is the number of nodes and e is the number of edges in the graph.
Average Case: O(n + e), as DFS will visit each node and edge at most once.
Worst Case: O(n + e), since each node and edge must be processed during DFS traversal.
Description: The time complexity is linear in terms of the number of nodes and edges in the graph.
Best Case: O(n), since the space needed to store node status and recursion stack is proportional to the number of nodes.
Worst Case: O(n), as we need to store the status of each node during the DFS traversal.
Description: The space complexity is linear with respect to the number of nodes in the graph.
