Categories: Graph/DFS

Level: Medium

Introduction: (Basic + Advanced + Interview Edition) 
Learning Algorithms from LeetCode + Interview Success Guide 
(Regular price: 3591 NTD, Discounted price until 2024/05/16 23:59)
https://hiskio.com/bundles/egb397?s=tc

(Regular price: 3990 NTD, Valid for a long term) 
https://bit.ly/lc2022all

Please help me click on the “SHOW EMBED” below and give it 5 likes~ If you like it, you can also give me a round of applause~ 
(Liking doesn’t cost anything, thank you for supporting my writing~)

Question

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

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** (or another safe node).

Return an array containing all the *safe nodes * of the graph. The answer should be sorted in ascending order.

Example 1

1
2
3
4
5

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
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

1
2
3

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:

Constraints

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[i] is sorted in a strictly increasing order.
• The graph may contain self-loops.
• The number of edges in the graph will be in the range [1, 4 * 104].

Analysis/Approach:

There is a directed graph with n nodes, each labeled from 0 to n-1. The graph is represented using a 2D array called “graph,” where graph[i] represents the nodes connected to node i with an edge. The direction of the edge is from node i to each node in graph[i]. If a node has no outgoing edges , it is considered a terminal node . If all possible paths from a node ** lead to terminal nodes**, the node is considered a ** safe node**.

The task is to find all the safe nodes in the graph and return them in ascending order as an array (or list). To determine if a node is a safe node, we need to check if there are any cycles in the paths starting from that node. ** If there is a cycle, the node itself and all the nodes in the cycle will not be safe nodes.** Additionally, since we need to check that all paths are cycle-free to determine a safe node, ** the results from earlier checks for nodes can be applied to later checks.**

To solve this problem, we can use a depth-first search (DFS ) approach to traverse each node and its paths until the end (or until we can determine if there is a cycle). The steps for solving the problem are as follows:

1. Initialize two arrays/lists, vis and ** path**, to keep track of whether a node has been visited and whether it is part of a cycle. Both arrays/lists should have a length equal to the number of nodes in the graph, n, and initialized with 0 (or False).
2. Initialize an empty result list called res .
3. Declare a DFS function that takes the current node, graph , vis , and path as parameters and returns ** True if a cycle is found** and ** False if no cycle is found**.
4. In the DFS function, perform the following steps: 
   4.1. Set vis[curr] and ** path[curr]** to ** 1** (indicating that the node has been visited and is temporarily part of a cycle). 
   4.2. Iterate over the nodes u in graph[curr] : 
   4.2.1. If vis[u] is 0 (indicating that the node hasn’t been visited), recursively call DFS with u as the current node and check if it returns True. ** If True, return True (indicating a cycle is found). 
   4.2.2. Otherwise, if path[u] == 1 (indicating that u is already part of a cycle), return ** True. 
   4.3. After the loop ends without returning True , it means there is no cycle found when going down from the current node. ** Reset path[curr] to 0 and return False. (Since we set all the path[curr] alone with 1, we need to set it back)**
5. In the main function, use a loop to iterate over i from 0 to n-1 . If vis[i] is 0, call DFS with i as the current node.
6. After all iterations, use another loop to iterate over i from 0 to n-1 and add the nodes i with path[i] == 0 to the res list.
7. Return the res list.

Here is the code implementation in both Java and Python:

Java

In the Java implementation, an ArrayList is used for the res variable. If we want to reduce the number of parameters passed to the dfs function, we can make vis and path class variables. However, since their lengths are tied to the number of nodes in the graph, they still need to be initialized within the eventualSafeNodes method.

Python

As mentioned before, in the Python implementation, using nested functions can slightly reduce the number of variables that need to be passed as arguments. In fact, if we move the vis and path arrays/lists to the outermost scope, they don’t need to be passed as arguments at all because the nested function can access variables from the outer scope.

You may try rewriting the code and experimenting with this approach.

Potential Interview Questions:
“What are the time and space complexities?”
(O(V+E)/O(V) , where V is the number of nodes in the graph and E is the number of edges in the graph)

“Can we use a single array/list to handle visited nodes and cycles?” (Hint: State can have more than 1 or 0; 
you can use 3 different states to handle this)

Similar and Extended Topics:
Special thanks to suggestions/corrections from viewers:
(Welcome to provide feedback to help with corrections~)

Learn Algorithms from LeetCode — See you next time!

Want to see more problems? 
Feel free to check out Article 0 for the topic you want!

Also, follow our Facebook page for notifications on new articles:
Learn with Desolve