#802

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Find Eventual Safe States

Solve the problem of finding eventual safe states in a directed graph using depth-first search and topological sorting.

depth first search breadth first search graph topological sort

Problem Statement

You are given a directed graph of n nodes labeled from 0 to n - 1. The graph is represented as a 2D integer array where graph[i] contains the nodes that node i points to. A node is a terminal node if it has no outgoing edges. A safe node is one that can only reach terminal nodes or other safe nodes via a valid path.

Return an array containing all the safe nodes in ascending order. The graph may contain cycles, and nodes with self-loops are allowed. The challenge is to efficiently determine which nodes can eventually reach terminal nodes without leading to a cycle.

Examples

Example 1

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output: [2,4,5,6]

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

Output: [4]

Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

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].

Solution Approach

Graph Traversal with Depth-First Search (DFS)

Start by performing a depth-first search (DFS) from each node. Track the state of each node (unvisited, visiting, or safe) to avoid revisiting nodes and to detect cycles. A node is safe if all its descendants either lead to terminal nodes or other safe nodes.

Topological Sorting with Indegree

Use topological sorting based on indegree to process nodes in the correct order. Nodes with zero indegree (no outgoing edges) are terminal and safe by definition. Gradually remove nodes from the graph and adjust the indegree to identify further safe nodes.

BFS for Efficiency

Breadth-first search (BFS) can be employed to process nodes level by level, starting with the terminal nodes. This helps in efficiently determining the safe nodes by propagating the safety of terminal nodes through the graph.

Complexity Analysis

Metric	Value
Time	O(m + n)
Space	O(n)

The time complexity of this solution is O(m + n), where m is the number of edges and n is the number of nodes. This is due to the need to visit each node and edge during the traversal. The space complexity is O(n) for storing the state of each node and the graph structure.

What Interviewers Usually Probe

Look for the candidate's understanding of graph traversal techniques like DFS and BFS.
Check if the candidate can implement topological sorting or manage indegree calculations effectively.
Ensure that the candidate can handle graph cycles and efficiently determine safe nodes.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly identify cycles, leading to incorrect results for non-terminal nodes.
Not updating node states correctly during the DFS, resulting in missing safe nodes.
Inaccurate handling of nodes with self-loops, which may cause confusion during graph traversal.

Follow-up variants

Adapt the problem to handle graphs with a larger number of nodes or edges.
Extend the problem to detect multiple types of cycles, not just those involving terminal nodes.
Modify the graph to allow for weighted edges, which would impact the safety of nodes.

FAQ

What is the primary algorithmic pattern for solving Find Eventual Safe States?

The primary pattern involves using graph indegree and topological sorting to identify safe nodes in a directed graph.

What is the role of DFS in solving this problem?

DFS is used to explore each node's descendants, marking nodes as safe or not based on whether they lead to terminal nodes or cycles.

Can BFS be used instead of DFS for this problem?

Yes, BFS can also be used to efficiently propagate safety from terminal nodes across the graph.

How does graph indegree help in identifying safe nodes?

Nodes with zero indegree are terminal nodes, and by reducing indegree and checking for cycles, we can identify safe nodes.

What should I consider when dealing with cycles in the graph?

Cycles must be detected to avoid incorrectly marking nodes as safe. Proper node state tracking in DFS is essential for this.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        rg = defaultdict(list)
        indeg = [0] * len(graph)
        for i, vs in enumerate(graph):
            for j in vs:
                rg[j].append(i)
            indeg[i] = len(vs)
        q = deque([i for i, v in enumerate(indeg) if v == 0])
        while q:
            i = q.popleft()
            for j in rg[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return [i for i, v in enumerate(indeg) if v == 0]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        rg = defaultdict(list)
        indeg = [0] * len(graph)
        for i, vs in enumerate(graph):
            for j in vs:
                rg[j].append(i)
            indeg[i] = len(vs)
        q = deque([i for i, v in enumerate(indeg) if v == 0])
        while q:
            i = q.popleft()
            for j in rg[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return [i for i, v in enumerate(indeg) if v == 0]

Continue Practicing

#1203 sort items by groups respecting dependencies #329 longest increasing path in a matrix #310 minimum height trees