Leetcode 802. Find Eventual Safe States

Problem Explanation

We have a directed graph represented as a 2D array. A graph is a combination of nodes and edges. The nodes in this graph are represented as numbers 0 to N-1, where N is the length of the graph. The edges are described by nested lists; the index of the outer list is the starting node, and the elements of the inner list are the nodes that the starting node points to.

For example, a graph [[1,2],[2,3],[5],[0],[5],[],[]] describes a graph where node 0 points to nodes 1 and 2, node 1 points to node 2 and 3, node 2 points to node 5, and so on.

A node is considered safe if we must eventually walk to a terminal node. A terminal node is defined as a node that has no outgoing directed edges, that is, it does not point to any node. To explain it with an example, let's consider node '1' from above graph.

1    1
2   / \
3  2 - 3
4  

Initially we are at node '1'. It has outgoing edges to nodes '2' and '3'. If we chose the path to node '3', we will reach a terminal node as '3' does not have any outgoing edges. But, if we chose path to node '2', we will again have a choice to either stop at '2' which would lead to a terminal node or take the path to '3'. Thus, eventually, irrespective of path chosen at node '2', we will reach a terminal node. Hence, node '1' is a safe node.

We have to find all such safe nodes from the graph.

Solution Approach

We will use depth first search for this problem. The important point to note here is that, we only need to prove that from a given node, we can 'eventually' reach a terminal node. Hence, we do not need to visit each node. We can stop whenever a terminal node is reached.

We will create an array to keep track of the state of each node while performing the DFS. Possible states of a node are: Not visited, Visiting, Visited.

'Not Visited' state will be the initial state of all nodes. 'Visiting' will be the state when we are currently at a node and checking its connected nodes. 'Visited' will be the state when we have finished exploring all connected nodes of a node and it did not lead to a non-terminating path.

We start traversing the nodes starting from node 0. Whenever we reach a node, we mark it as 'Visiting'. We then check its connected nodes. If any of the connected nodes is currently being visited ('Visiting' state), it means there is a cycle and that would lead to a non-terminating path. Hence, we return 'False' in such a case. If the connected node is 'Visited', it means we have already evaluated this path and it is safe, so we ignore it and check other connected nodes. If all connected nodes are safe, we mark the current node as 'Visited' and return 'True'. If a node is evaluated as safe, we add it to the output list.

In the end, we have our list of safe nodes.

Solution in C++

1
2cpp
3enum State { kInit, kVisiting, kVisited };
4
5class Solution {
6public:
7  vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
8     //A list to keep all safe nodes.
9    vector<int> result;
10    //A list to keep track of state of each node.
11    vector<State> states(graph.size());
12
13    for (int i = 0; i < graph.size(); ++i)
14      if (!hasCycle(graph, i, states))
15        result.push_back(i);
16
17    return result;
18  }
19
20private:
21  bool hasCycle(const vector<vector<int>>& graph, int node, vector<State>& states) {
22    if (states[node] == State::kVisiting)
23      return true;
24    if (states[node] == State::kVisited)
25      return false;
26
27    states[node] = State::kVisiting;
28    for (const int connectedNode : graph[node])
29      if (hasCycle(graph, connectedNode, states))
30        return true;
31    states[node] = State::kVisited;
32
33    return false;
34  }
35};
36

The hasCycle function is performing DFS for a given node and its connected components. It returns 'True' if a cycle is detected, otherwise 'False'. If 'False' is returned for a node, it is added to the result list.## Solution in Python Let's follow the same approach to solve this problem in Python. The Pythonic way of representing the states would be using a dictionary where the key would be the node and the value would be its state.

1
2python
3# Enum names will be useful as identifiers for state of nodes.
4class State(): 
5    kInit = "INIT"
6    kVisiting = "VISITING"
7    kVisited = "VISITED"
8    
9def eventualSafeNodes(graph):
10    # Preparing the dictionary to keep states of nodes.
11    states = {node: State.kInit for node in range(len(graph))}
12    safe_nodes = []
13
14    # Function to perform DFS and detect cycles.
15    def hasCycle(node):
16        if states[node] == State.kVisiting:
17            return True
18        if states[node] == State.kVisited:
19            return False
20
21        states[node] = State.kVisiting
22        if any(hasCycle(neighbour) for neighbour in graph[node]):
23            return True
24        states[node] = State.kVisited
25        return False
26
27    # Main function to iterate over nodes and determine their safety.
28    for i in range(len(graph)):
29        if not hasCycle(i):
30            safe_nodes.append(i)
31    return safe_nodes

Solution in JavaScript

The concept remains the same in JavaScript as well. Let's see the JavaScript equivalent of the problem solution.

1
2javascript
3function eventualSafeNodes(graph) {
4    const INIT = 0,
5    VISITING = 1,
6    VISITED = 2;
7
8    let states = new Array(graph.length).fill(INIT);
9    let safeNodes = [];
10
11    function hasCycle(node){
12        if (states[node] === VISITING) return true;
13        if (states[node] === VISITED) return false;
14
15        states[node] = VISITING;
16        for(let nextNode of graph[node]){
17            if(hasCycle(nextNode)) return true;
18        }
19        states[node] = VISITED;
20        return false;
21    }
22
23    for(let i=0; i < graph.length; i++){
24        if(!hasCycle(i)) safeNodes.push(i);
25    }
26
27    return safeNodes;
28}

Solution in Java

In Java, the approach is consistent with other languages, with minor syntax alterations.

1
2java
3public List<Integer> eventualSafeNodes(int[][] graph) {
4    List<Integer> result = new ArrayList<>();
5    int[] color = new int[graph.length];
6    
7    for(int i=0; i<graph.length; i++){
8        if(DFS(i, color, graph)){
9            result.add(i);
10        }
11    }
12    
13    Collections.sort(result);
14    return result;
15}
16
17public boolean DFS(int i, int[] color, int[][] graph){
18    if(color[i] > 0)
19        return color[i] == 2;
20    
21    color[i] = 1;
22    for(int x: graph[i]){
23        if(!DFS(x, color, graph))
24            return false;
25    }
26    
27    color[i] = 2;
28    return true;
29}

Here, DFS is the function that is performing Depth-First Search for a given node and its connected components, returning 'false' if a cycle is detected, otherwise 'true'. If 'true' is returned for a node, it is added to the result list.

The Java solution involves use of an array 'color' which is serving similar purpose as the 'states' list in the previous solutions. The array contains integers where 0 represents 'red' or 'Init', 1 represents 'grey' or 'Visiting', and 2 represents 'black' or 'Visited'.

The eventualSafeNodes function checks all nodes in the graph, and if they are safe (i.e., they don't create a cycle), they are added to the result which is then sorted and returned.

The DFS function does most of the work which is identifying the cycles. If a node is found to be part of a cycle, it is removed from the graph. If all outgoing nodes from a given node are visited and found safe, the node is marked safe too.