• Expected Output: [0,1,2,3,4]
• Explanation:
  • Node 3 is a terminal node.
  • Node 2 leads to node 3, which is a terminal node.
  • Node 1 leads to node 2, which is a safe node, and node 3, which is a terminal node.
  • Similarly, all node leads to either a terminal or a safe node.

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 * 10⁴].

Solution

To solve this problem, we will use a depth-first search (DFS) approach to explore each node and its connections. We'll mark nodes as "safe" or "unsafe" based on whether all paths from the node lead to terminal nodes. This is efficient because we can mark nodes during the DFS traversal and avoid reprocessing them.

This approach works well because we only visit each node a limited number of times, leading to an overall efficient solution. By marking nodes as we determine their status, we avoid unnecessary re-computation. This is particularly useful for graphs, where cycles and repeated paths are common.

Step-by-Step Algorithm

1. Initialize variables:

   • Create an array visited of size n (number of nodes) and set all elements to 0. This array keeps track of the state of each node: 0 means unvisited, 1 means visiting, and -1 means safe.
   • Create an empty list result to store the safe nodes.

2. Define a DFS function:

   • If the current node is marked as safe (-1), return True.
   • If the current node is marked as visiting (1), return False to indicate a cycle.
   • Mark the current node as visiting (1).
   • Iterate through all adjacent nodes of the current node:
     • Recursively call the DFS function on each adjacent node.
     • If any adjacent node returns False, mark the current node as unsafe and return False.
   • Mark the current node as safe (-1).
   • Return True to indicate the current node is safe.

3. Process each node:

   • Iterate through each node from 0 to n-1.
   • For each node, call the DFS function. If the function returns True, add the node to the result list.

4. Sort and return the result:

   • Sort the result list in ascending order.
   • Return the result list.

Algorithm Walkthrough

Let's walk through the algorithm step-by-step using the graph [[1,2],[2,3],[2],[],[5],[6],[]]:

Graph representation:

• Node 0 -> [1, 2]
• Node 1 -> [2, 3]
• Node 2 -> [2]
• Node 3 -> []
• Node 4 -> [5]
• Node 5 -> [6]
• Node 6 -> []

Initial state:

• visited = [0, 0, 0, 0, 0, 0, 0]
• result = []

Step-by-step DFS calls:

1. Processing node 0:

   • DFS(0) is called.
   • visited[0] is marked as 1.
   • Processing adjacent node 1 of node 0:
     • DFS(1) is called.
     • visited[1] is marked as 1.
     • Processing adjacent node 2 of node 1:
       • DFS(2) is called.
       • visited[2] is marked as 1.
       • Processing adjacent node 2 of node 2:
         • DFS(2) is called.
         • visited[2] is already 1 (cycle detected).
         • Return False.
       • visited[2] remains 1 (unsafe).
       • Return False.
     • visited[1] remains 1 (unsafe).
     • Return False.
   • visited[0] remains 1 (unsafe).
   • Return False.

2. Processing node 1:

   • DFS(1) is called.
   • visited[1] is already 1 (unsafe).
   • Return False.

3. Processing node 2:

   • DFS(2) is called.
   • visited[2] is already 1 (unsafe).
   • Return False.

4. Processing node 3:

   • DFS(3) is called.
   • visited[3] is marked as 1.
   • Node 3 has no adjacent nodes.
   • visited[3] is marked as -1 (safe).
   • Add node 3 to result.
   • result = [3]
   • Return True.

5. Processing node 4:

   • DFS(4) is called.
   • visited[4] is marked as 1.
   • Processing adjacent node 5 of node 4:
     • DFS(5) is called.
     • visited[5] is marked as 1.
     • Processing adjacent node 6 of node 5:
       • DFS(6) is called.
       • visited[6] is marked as 1.
       • Node 6 has no adjacent nodes.
       • visited[6] is marked as -1 (safe).
       • Add node 6 to result.
       • result = [3, 6]
       • Return True.
     • visited[5] is marked as -1 (safe).
     • Add node 5 to result.
     • result = [3, 6, 5]
     • Return True.
   • visited[4] is marked as -1 (safe).
   • Add node 4 to result.
   • result = [3, 6, 5, 4]
   • Return True.

6. Processing node 5:

   • DFS(5) is called.
   • visited[5] is already -1 (safe).
   • Return True.

7. Processing node 6:

   • DFS(6) is called.
   • visited[6] is already -1 (safe).
   • Return True.

Final result:

• Sort result = [3, 4, 5, 6]
• Return [3, 4, 5, 6]

Code