DSA sheet · Graphs · Topological sort (BFS) pattern

Find Eventual Safe States

This is the third topological sort problem after Course Schedule I and II. The question looks new (it talks about "safe" and "terminal" nodes, not courses), but the teacher shows that it is the same indegree + queue idea with one twist: we run it on the reversed graph, starting from the terminal nodes and walking backwards. She also points out that the problem can be solved by cycle detection with DFS. She only codes the BFS method, so that is Part A. Part B gives the DFS method she mentions, so you have both ways in your pocket.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph basics you need for this page
• Part A · BFS topological sort on the reversed graph (the teacher's method)
• Part B · DFS with three colours (the cycle-detection method she mentions)
• Part C · Revision page

Part 0 · Graph basics

Nodes and edges

A graph is a set of points called nodes (or vertices) joined by lines called edges. Here the nodes are numbered 0 to n − 1.

• Undirected edge (0)—(1): you can walk both ways, 0 to 1 and 1 to 0.
• Directed edge (0)→(1): a one-way street. You can go from 0 to 1, but not back from 1 to 0. This problem uses only directed edges.
• Weighted edge (0)—5—(1): the edge carries a number (a cost, a distance). This problem has no weights. Every edge is just "you can go there".

Out-degree and in-degree

   (0) ──→ (1)
    │
    ↓
   (2) ──→ (1)       out-degree of 0 = 2   (two arrows leave 0)
                     in-degree  of 1 = 2   (two arrows enter 1)
                     out-degree of 1 = 0   (nothing leaves 1)

• Out-degree of a node = how many arrows leave it.
• In-degree of a node = how many arrows enter it.

Three ways the input can come

This problem already gives an adjacency list, called graph. If you get an edge list instead, this is how you build one:

n = 3
edges = [[0, 1], [0, 2], [2, 1]]
adj = [[] for _ in range(n)]      # one empty list per node
for a, b in edges:
    adj[a].append(b)              # directed: only a -> b
    # for an undirected graph you would also do adj[b].append(a)
print(adj)                        # [[1, 2], [], [1]]

Visited, and connected components

A graph can have loops, so a walk could come back to the same node forever. We keep a visited set (or a list of True/False) and never process a node twice. A connected component is a group of nodes that can reach each other. A graph can have several separate groups, so traversal code usually loops over every node and starts a new search from each unvisited one.

BFS and DFS in one picture

from collections import deque

adj = [[1, 2], [3], [3], []]

def bfs(start):
    seen = [False] * len(adj)
    seen[start] = True
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()          # take from the front
        order.append(node)
        for nb in adj[node]:
            if not seen[nb]:
                seen[nb] = True         # mark when you push
                queue.append(nb)
    return order

def dfs(node, seen, order):
    seen[node] = True
    order.append(node)
    for nb in adj[node]:
        if not seen[nb]:
            dfs(nb, seen, order)        # go deep first
    return order

print(bfs(0))                            # [0, 1, 2, 3]
print(dfs(0, [False] * 4, []))           # [0, 1, 3, 2]

Grids are graphs too (not needed here, but good to know)

In grid problems each cell is a node, and its neighbours are the cells up, down, left and right. We loop over four direction pairs (dr, dc), check the new cell is inside the grid (the bounds check), and often mark visited cells by changing the grid itself.

grid = ["11", "01"]
rows, cols = len(grid), len(grid[0])
r, c = 0, 1
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:      # bounds check
        print((nr, nc), grid[nr][nc])
# prints (1, 1) 1  and  (0, 0) 1

Cycles in a directed graph

A cycle is a path that comes back to where it started, like (0)→(1)→(3)→(0). Once you are on a cycle you can walk round and round forever. This matters a lot for today's problem.

Kahn's algorithm (topological sort with BFS), recap from Course Schedule

A topological order lists the nodes so that every arrow points forward (a before b for every a → b). Kahn's algorithm builds it like this:

1. Count the in-degree of every node.
2. Put every node with in-degree 0 in a queue (nothing has to come before them).
3. Pop a node, write it in the answer, and for each child reduce its in-degree by 1 (as if we deleted the arrow). If a child's in-degree becomes 0, push it.
4. Nodes on a cycle never reach in-degree 0, so they never enter the queue.

from collections import deque

def topo(n, adj):
    indeg = [0] * n
    for a in range(n):
        for b in adj[a]:
            indeg[b] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for b in adj[node]:
            indeg[b] -= 1               # "remove" the arrow node -> b
            if indeg[b] == 0:
                queue.append(b)
    return order                        # shorter than n means a cycle exists

print(topo(4, [[1, 2], [3], [3], []]))  # [0, 1, 2, 3]
print(topo(2, [[1], [0]]))              # []

Reversing a graph

Reversing means turning every arrow round: a → b becomes b → a. In the reversed list, rev[b] holds the nodes that point to b in the original graph (its parents). Note: the original out-degree of a node equals its in-degree in the reversed graph. This one fact is the key to Part A.

graph = [[1, 2], [2], []]           # 0->1, 0->2, 1->2
rev = [[] for _ in range(len(graph))]
for node in range(len(graph)):
    for nb in graph[node]:
        rev[nb].append(node)          # arrow node->nb becomes nb->node
print(rev)                            # [[], [0], [0, 1]]

Part A · BFS topological sort on the reversed graph

LeetCode 802 · Find Eventual Safe States

1The question in simple words

You get a directed graph with nodes 0 … n−1 as an adjacency list graph, where graph[i] lists the nodes that i points to.

• A terminal node is a node with no outgoing edges (its list is empty). From it you can't go anywhere.
• A safe node is a node where every possible path starting from it ends at a terminal node. Not "some path": every path.

Return all safe nodes, sorted in increasing order.

        ┌─────────────────┐
        ↓                 │
       (0) ───→ (1) ───→ (3)
         ╲       │
          ╲      ↓
           ───→ (2) ───→ (5) ←─── (4)

                                   (6)

Edges: 0→1, 0→2, 1→2, 1→3, 2→5, 3→0, 4→5. Nodes 5 and 6 have empty lists. Answer: [2, 4, 5, 6].

2What the constraints tell us

• 1 ≤ n ≤ 10⁴ nodes and at most 4 × 10⁴ edges in total → we want something close to O(n + E). Something like "for every node, explore every path" can blow up, because the number of paths can grow very fast.
• graph[i] is sorted and has no repeats, but it can contain i itself (a self-loop like 1 → 1). A self-loop is a tiny cycle, so such a node can never be safe. Our method must handle it (it does, see Doubt 5).
• The answer must be sorted. The teacher uses that to save a sort at the end (step 4).

3Intuition: a mental picture

Think of the terminal nodes as exits of a building, and the arrows as one-way corridors. A room is safe if, whatever corridor you choose, you always end up at an exit. A room is unsafe if some choice lets you wander in a loop forever.

Instead of standing in each room and trying every corridor, we start at the exits and walk the corridors backwards. A room becomes safe the moment all of its corridors are known to lead to safe rooms. Walking backwards = using the reversed graph. Counting "how many of my corridors are still unknown" = the out-degree counter, used exactly like the in-degree in Kahn's algorithm.

4Building the logic from the teacher's examples

Terminal nodes are safe

5 and 6 have no outgoing edges. Every path that starts at 5 is just "5", and it ends at a terminal node. So every terminal node is also a safe node.

Node 4: one corridor, it goes to an exit → safe

From 4 the only move is to 5, which is terminal. Every path from 4 ends at a terminal node → 4 is safe. Same for 2: its only move is to 5 → 2 is safe.

Node 3: "every path", not "some path"

The teacher walks from 3: 3 → 0 → 2 → 5. That reaches a terminal node, so you might call 3 safe. But wait: from 0 you could also go to 1, and from 1 to 3, and from 3 back to 0 … The walk 3 → 0 → 1 → 3 → 0 → 1 → … never reaches a terminal node. One bad path is enough → 3 is not safe.

Nodes 0 and 1 have the same problem: each of them has a path into the loop 0 → 1 → 3 → 0. So 0, 1, 3 are unsafe.

A cycle means not safe

The teacher's conclusion from node 3: a node that sits on a cycle can never be safe. A node on a cycle has at least one outgoing edge (the one that continues the cycle), so it's not terminal, and following the cycle gives a path that never ends.

That's why the teacher says the problem can be solved in two ways: by detecting cycles (Part B), or by topological sort (this part).

Why not start from node 0 (the brute force idea)?

The natural first try: for each node, explore every path and check that all of them end at a terminal node. The teacher rejects this for node 0: from 0 you can't decide anything until you have explored every path from 0 to the very end. And then you do the same work again for 1, again for 3… The number of paths can be huge.

Better question: which node can I call safe right away, without exploring anything? The terminal nodes. If a graph has no terminal node at all, then nothing is safe, so the terminal nodes are the natural place to start.

How do we find terminal nodes? Out-degree 0

"No outgoing edges" is exactly out-degree 0. The teacher counts them for Example 1:

5 and 6 have out-degree 0 → they are terminal → safe → they go into the queue first.

From a safe node, walk backwards

Pop 5. Who points to 5? Nodes 2 and 4. Their arrows into 5 now lead to a safe place, so each of them has one fewer unknown corridor. Reduce their out-degree by 1: 2 goes 1 → 0, and 4 goes 1 → 0. Out-degree 0 now means "all my corridors lead to safe nodes" → 2 and 4 are safe → push them.

Building the reversed list for Example 1 (the teacher does it by hand, reading each list "the other way"): 0 has children 1, 2 → write 0 into rev[1] and rev[2]. 1 has children 2, 3 → write 1 into rev[2] and rev[3]. And so on:

        ┌─────────────────┐
        │                 ↓
       (0) ←─── (1) ←─── (3)
         ↖       ↑
          ╲      │
           ──── (2) ←─── (5) ───→ (4)

                                   (6)

Popping 2: the counter stops the cycle nodes

Pop 2. rev[2] = [0, 1]. Reduce: 0 goes 2 → 1, 1 goes 2 → 1. Both are still positive: each of them has one more corridor whose safety we don't know (0 → 1 and 1 → 3). So we don't push them. Nobody will ever reduce those last counters, because the nodes at the other end (1 and 3) are on the cycle and never become safe. The queue empties, and 0, 1, 3 are left out. ✓

The teacher links this back to Course Schedule I and II: pop, reduce the counter of each neighbour, push it when the counter hits 0. If that part feels unclear, revise those pages first.

Returning the answer in sorted order without sorting

The popped nodes come out as 5, 6, 2, 4, not sorted. Two options:

• Collect them in a list and call sort() → O(k log k) for k safe nodes, which is O(n log n) in the worst case (all nodes safe).
• The teacher's trick: keep a True/False list safe of size n. Mark safe[node] = True when you pop. At the end, walk i = 0 … n−1 and collect the indices that are True. They come out already sorted, in O(n). She notes this costs an extra O(n) array, so it's a trade: a little space to save the n log n.

She also says this sorting trick isn't part of the graph logic. It's just a small optimisation you can come up with yourself.

5Approach steps

1. Build rev, the reversed graph, and outdeg[node] = length of graph[node].
2. Push every node with outdeg 0 (the terminal nodes) into a queue.
3. While the queue isn't empty: pop a node and mark it safe.
4. For each prev in rev[node] (each node that points to it), reduce outdeg[prev] by 1. If it becomes 0, all of prev's edges lead to safe nodes → push prev.
5. Walk 0 … n−1 and return the indices marked safe (already sorted).

6Code (Python)

from collections import deque

class Solution:
    def eventualSafeNodes(self, graph):
        n = len(graph)
        rev = [[] for _ in range(n)]      # reversed graph
        outdeg = [0] * n                  # = in-degree in the reversed graph
        for node in range(n):
            for nb in graph[node]:
                rev[nb].append(node)      # arrow node->nb becomes nb->node
                outdeg[node] += 1

        queue = deque()
        for i in range(n):
            if outdeg[i] == 0:            # terminal nodes are safe
                queue.append(i)

        safe = [False] * n
        while queue:
            node = queue.popleft()
            safe[node] = True
            for prev in rev[node]:        # nodes that point to this safe node
                outdeg[prev] -= 1
                if outdeg[prev] == 0:     # all its edges lead to safe nodes
                    queue.append(prev)

        result = []
        for i in range(n):                # walking 0..n-1 keeps it sorted
            if safe[i]:
                result.append(i)
        return result

7Code line by line

8Dry run on Example 1

Start: outdeg = [2, 2, 1, 1, 1, 0, 0], queue = [5, 6].

Collect in index order: safe = [F, F, T, F, T, T, T] → answer [2, 4, 5, 6] ✓

  (0) → (1) → (3) → back to (0)
   ↘     ↓
     → (2)✓ → (5)✓ ← (4)✓      (6)

  (0)✗ → (1)✗ → (3)✗ → back to (0)
   ↘      ↓
     → (2)✓ → (5)✓ ← (4)✓      (6)✓
  0, 1, 3 keep outdeg 1, 1, 1: stuck on the loop

The bug the teacher hit on screen

Her first run returned only [5, 6]. In the BFS loop she had written for prev in graph[node], the original list. graph[5] and graph[6] are empty, so nothing was ever reduced and nothing else entered the queue. The whole reason we built rev was to walk backwards. Switching the loop to rev[node] fixed it. (The test file runs this wrong version too and checks it gives [5, 6].)

Example 2 (from LeetCode), quickly

graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]. Only 4 is terminal. Pop 4: rev[4] = [0, 2, 3] → outdeg 0: 4→3, 2: 2→1, 3: 2→1. None reaches 0, so the queue empties. Answer [4]. Node 1 has a self-loop (1 → 1): its counter can only drop when 1 itself is popped, which never happens.

9Complexity & remember

• Time O(n + E). Building rev and outdeg touches each node and each edge once (not nested n × n, the inner loops add up to E in total). Finding terminal nodes is O(n). The BFS pops each node at most once and looks at each reversed edge at most once: O(n + E). Collecting the answer is O(n). All of it is linear.
• Space O(n + E). The reversed graph stores every edge once (directed). The teacher notes that an undirected graph stores each edge twice, n + 2E, but here it's one direction only. Plus O(n) for outdeg, O(n) for safe, and O(n) for the queue.
• The safe array costs O(n) extra space but saves an O(n log n) sort. Without it: less space, more time.

Part B · DFS with three colours

The teacher names this method ("detecting cycle") and sets it aside to focus on topo sort. It's written out here so the idea is complete.

1The question

Same question as Part A. From Doubt 1: a node is safe exactly when no path from it can reach a cycle. So we just need cycle detection, the same idea as Cycle in a Directed Graph (DFS).

2Constraints

Same as Part A. One extra worry for DFS: a long chain of 10⁴ nodes means recursion 10⁴ calls deep. Python's default limit is about 1000, so we raise it with sys.setrecursionlimit.

3Intuition

Walk forward from a node with DFS. Keep a colour for every node:

If DFS steps onto a grey node, it has walked back into its own current path, which is a cycle. Everything on that path is unsafe.

4Building the logic

• Reach a node already black → it's safe, answer True straight away.
• Reach a node that is grey → either it's on the current path (a cycle) or it was found unsafe earlier. Both mean False.
• A white node: paint it grey, then visit every child. If any child returns False, return False and leave the node grey. If all children are safe, paint it black and return True.

5Approach steps

1. state = [0] * n.
2. dfs(node): if state is not 0, return state == 2.
3. Set state 1. For each child: if dfs(child) is False, return False.
4. Set state 2 and return True.
5. Answer = every i from 0 to n−1 where dfs(i) is True (sorted for free).

6Code (Python)

import sys

class Solution:
    def eventualSafeNodes(self, graph):
        sys.setrecursionlimit(30000)
        n = len(graph)
        state = [0] * n          # 0 = new, 1 = on path / unsafe, 2 = safe

        def dfs(node):
            if state[node] != 0:
                return state[node] == 2
            state[node] = 1                  # grey: on the current path
            for nb in graph[node]:
                if not dfs(nb):
                    return False             # stays grey = unsafe
            state[node] = 2                  # black: every path is safe
            return True

        return [i for i in range(n) if dfs(i)]

7Code line by line

8Dry run on Example 1

1. dfs(0): grey. Child 1 → dfs(1): grey. Child 2 → dfs(2): grey. Child 5 → dfs(5): no children → black, True.
2. 2: all children safe → black, True. Back in dfs(1), next child 3 → dfs(3): grey. Child 0 → 0 is grey → False (a cycle 0 → 1 → 3 → 0).
3. 3 returns False (stays grey). 1 returns False (stays grey). 0 returns False (stays grey).
4. dfs(1), dfs(2), dfs(3) answer from their colour: False, True, False.
5. dfs(4): grey, child 5 is black → True → 4 black. dfs(5) True. dfs(6): no children → True.
6. Answer [2, 4, 5, 6] ✓

9Complexity & remember

• Time O(n + E): each node is turned grey only once, and each edge is followed at most once.
• Space O(n) for state and the recursion stack. No reversed graph needed.

Part C · Revision page

s = Solution()
print(s.eventualSafeNodes([[1, 2], [2, 3], [5], [0], [5], [], []]))       # [2, 4, 5, 6]
print(s.eventualSafeNodes([[1, 2], [2, 3], [5], [0], [5], [], [], [0]])) # [2, 4, 5, 6]
print(s.eventualSafeNodes([[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]))   # [4]
print(s.eventualSafeNodes([[]]))                                        # [0]
print(s.eventualSafeNodes([[0]]))                                       # []
print(s.eventualSafeNodes([[1], [2], [0]]))                             # []

Based on this video: Find Eventual Safe States | Topological Sort (BFS)