Minimum Number of Vertices to Reach All Nodes

▶

Steps

setup

Initialize in-degree and graph adjacency list

Create an in-degree list initialized to zero for all 6 nodes and an empty adjacency list for each node.

💡 This sets up the data structures needed to track incoming edges and neighbors for each node.

Line:

in_degree = [0] * n
graph = [[] for _ in range(n)]

💡 We need to know how many edges point to each node to find zero in-degree nodes.

fill_cells

Add edge 0 -> 1 and update in-degree of node 1

Add node 1 to adjacency list of node 0 and increment in-degree of node 1 by 1.

💡 Each edge increases the in-degree of the destination node, showing how many incoming edges it has.

Line:

graph[u].append(v)
in_degree[v] += 1  # for u=0, v=1

💡 Node 1 now has one incoming edge from node 0.

fill_cells

Add edge 0 -> 2 and update in-degree of node 2

Add node 2 to adjacency list of node 0 and increment in-degree of node 2 by 1.

💡 Updating in-degree helps identify nodes that have no incoming edges later.

Line:

graph[u].append(v)
in_degree[v] += 1  # for u=0, v=2

💡 Node 2 now has one incoming edge from node 0.

fill_cells

Add edge 2 -> 5 and update in-degree of node 5

Add node 5 to adjacency list of node 2 and increment in-degree of node 5 by 1.

💡 Edges from nodes with non-zero in-degree also affect reachability and must be tracked.

Line:

graph[u].append(v)
in_degree[v] += 1  # for u=2, v=5

💡 Node 5 now has one incoming edge from node 2.

fill_cells

Add edge 3 -> 4 and update in-degree of node 4

Add node 4 to adjacency list of node 3 and increment in-degree of node 4 by 1.

💡 Edges from disconnected components are also recorded to understand full graph structure.

Line:

graph[u].append(v)
in_degree[v] += 1  # for u=3, v=4

💡 Node 4 now has one incoming edge from node 3.

fill_cells

Add edge 4 -> 2 and update in-degree of node 2

Add node 2 to adjacency list of node 4 and increment in-degree of node 2 by 1 again (total 2).

💡 Multiple incoming edges increase in-degree accordingly, affecting when nodes enter the queue.

Line:

graph[u].append(v)
in_degree[v] += 1  # for u=4, v=2

💡 Node 2 now has two incoming edges (from 0 and 4).

setup

Identify zero in-degree nodes and initialize queue

Find nodes with zero in-degree (0 and 3) and add them to the queue and result list.

💡 Zero in-degree nodes are starting points that can reach others without dependencies.

Line:

queue = deque([i for i in range(n) if in_degree[i] == 0])
result = list(queue)

💡 Nodes 0 and 3 have no incoming edges and form the minimal set to reach all nodes.

traverse

Process node 0 from queue

Remove node 0 from queue, mark it done, and process its neighbors 1 and 2 by decrementing their in-degree.

💡 Processing a node simulates removing it and updating neighbors' in-degree to find new zero in-degree nodes.

Line:

node = queue.popleft()  # node=0
for nei in graph[node]:
    in_degree[nei] -= 1

💡 Decrementing in-degree may create new zero in-degree nodes to add to the queue.

traverse

Process neighbor 1 of node 0

After decrementing in-degree of node 1 to zero, add node 1 to the queue.

💡 Nodes enter the queue only when their in-degree reaches zero, meaning all dependencies are processed.

Line:

if in_degree[nei] == 0:
    queue.append(nei)  # nei=1

💡 Node 1 is now reachable from processed nodes and ready to be processed itself.

traverse

Process neighbor 2 of node 0

Decrement in-degree of node 2 from 2 to 1; since it is not zero, do not add to queue.

💡 Nodes with in-degree > 0 still have dependencies and cannot be processed yet.

Line:

in_degree[nei] -= 1  # nei=2
if in_degree[nei] == 0:
    queue.append(nei)

💡 Node 2 still depends on other nodes and must wait.

traverse

Process node 3 from queue

Remove node 3 from queue, mark done, and process its neighbor 4 by decrementing in-degree.

💡 Processing node 3 explores another disconnected component and updates its neighbors.

Line:

node = queue.popleft()  # node=3
for nei in graph[node]:
    in_degree[nei] -= 1

💡 Decrementing in-degree of node 4 may enable it to enter the queue.

traverse

Process node 1 from queue

Remove node 1 from queue and mark it done. Node 1 has no neighbors, so no in-degree updates.

💡 Nodes without neighbors simply get marked done and do not affect others.

Line:

node = queue.popleft()  # node=1
for nei in graph[node]:
    in_degree[nei] -= 1

💡 Node 1 is reachable and processed, but does not unlock any new nodes.

traverse

Process node 4 from queue

Remove node 4 from queue, mark done, and process its neighbor 2 by decrementing in-degree.

💡 Processing node 4 reduces in-degree of node 2, potentially unlocking it.

Line:

node = queue.popleft()  # node=4
for nei in graph[node]:
    in_degree[nei] -= 1

💡 Node 2's in-degree decreases from 1 to 0, so it can be added to the queue.

traverse

Process node 2 from queue

Remove node 2 from queue, mark done, and process its neighbor 5 by decrementing in-degree.

💡 Processing node 2 unlocks node 5 by reducing its in-degree.

Line:

node = queue.popleft()  # node=2
for nei in graph[node]:
    in_degree[nei] -= 1

💡 Node 5's in-degree decreases from 1 to 0, so it can be added to the queue.

traverse

Process node 5 from queue

Remove node 5 from queue and mark done. Node 5 has no neighbors, so no further updates.

💡 Processing leaf nodes completes the traversal without unlocking new nodes.

Line:

node = queue.popleft()  # node=5
for nei in graph[node]:
    in_degree[nei] -= 1

💡 All nodes reachable from zero in-degree nodes have been processed.

reconstruct

Return minimal set of vertices with zero in-degree

Return the initial zero in-degree nodes [0, 3] as the minimal set to reach all nodes.

💡 These nodes are the minimal starting points to cover the entire graph.

Line:

return result

💡 The minimal set is exactly the nodes that started with zero in-degree.

from collections import deque

def findSmallestSetOfVertices(n, edges):
    in_degree = [0] * n  # STEP 1
    graph = [[] for _ in range(n)]  # STEP 1
    for u, v in edges:  # STEP 2-6
        graph[u].append(v)  # STEP 2-6
        in_degree[v] += 1  # STEP 2-6

    queue = deque([i for i in range(n) if in_degree[i] == 0])  # STEP 7
    result = list(queue)  # STEP 7

    while queue:  # STEP 8-15
        node = queue.popleft()  # STEP 8,11,12,13,14,15
        for nei in graph[node]:  # STEP 8,11,13,14
            in_degree[nei] -= 1  # STEP 8,11,13,14
            if in_degree[nei] == 0:  # STEP 9,13,14
                queue.append(nei)  # STEP 9,13,14

    return result  # STEP 16

if __name__ == '__main__':
    n = 6
    edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
    print(findSmallestSetOfVertices(n, edges))

📊

Minimum Number of Vertices to Reach All Nodes - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how in-degree relates to reachability and why nodes with zero in-degree form the minimal starting set.

Visiting: none

0

1

2

3

4

5

Visiting: 0

Edge: 0 → 1

0

1

2

3

4

5

Visiting: 0

Edge: 0 → 2

0

1

2

3

4

5

Visiting: 2

Edge: 2 → 5

0

1

2

3

4

5

Visiting: 3

Edge: 3 → 4

0

1

2

3

4

5

Visiting: 4

Edge: 4 → 2

0

1

2

3

4

5

Visiting: none

0

1

2

3

4

5

Queue / Stack

03

Visiting: 0

Edge: 0 → 1

0

1

2

3

4

5

Queue / Stack

31

Visiting: 0

Edge: 0 → 1

0

1

2

3

4

5

Queue / Stack

31

Visiting: 0

Edge: 0 → 2

0

1

2

3

4

5

Queue / Stack

31

Visiting: 3

Edge: 3 → 4

0

1

2

3

4

5

Queue / Stack

14

Visiting: 1

0

1

2

3

4

5

Queue / Stack

4

Visiting: 4

Edge: 4 → 2

0

1

2

3

4

5

Queue / Stack

2

Visiting: 2

Edge: 2 → 5

0

1

2

3

4

5

Queue / Stack

5

Visiting: 5

0

1

2

3

4

5

Visiting: none

0

1

2

3

4

5

Key Takeaways

✓ Nodes with zero in-degree form the minimal set of vertices to reach all nodes.

This is hard to see from code alone because it requires understanding the relationship between in-degree and reachability.

✓ Decrementing in-degree during traversal reveals when nodes become reachable and ready to process.

Visualizing in-degree changes clarifies why nodes enter the queue only after all dependencies are processed.

✓ Disconnected components and cycles do not affect the minimal set beyond their zero in-degree nodes.

The trace shows how separate components are handled independently by the queue initialization.

Practice

1. Consider the following Python code implementing bidirectional BFS to find the shortest path in a binary matrix. Given the input grid below, what is the returned shortest path length?

grid = [
  [0, 1, 0],
  [1, 0, 0],
  [1, 1, 0]
]

# Code snippet uses the bidirectional BFS approach as described.

What is the output of shortestPathBinaryMatrix(grid)?

easy

A. 3

B. 5

C. -1

D. 4

Solution

1. Step 1: Trace BFS from start (0,0)

   Start at (0,0) with distance 1. Neighbors reachable: (1,1) at distance 2.

2. Step 2: Trace BFS from end (2,2)

   Start at (2,2) with distance 1. Neighbors reachable: (1,2) at distance 2, (1,1) at distance 2.

3. Step 3: Meeting point

   Both searches meet at (1,1). Sum distances: 2 (start side) + 2 (end side) = 4, but since both include the meeting cell, shortest path length is 3.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shortest path length is 3 steps [OK]

Hint: Bidirectional BFS meets in middle, sum distances minus 1 [OK]

Common Mistakes:

• Off-by-one in path length
• Ignoring meeting cell counted twice

2. What is the time complexity of the optimal Kahn's Algorithm solution for the Course Schedule problem, given V courses and E prerequisite pairs?

medium

A. O(V + E) because each node and edge is processed once in BFS

B. O(V * E) due to nested loops over nodes and edges

C. O(V^2) because each node might be checked against all others

D. O(E) only, since edges dominate the processing time

Solution

1. Step 1: Identify operations on nodes and edges

   Each node is enqueued and dequeued once; each edge is visited once when decrementing in-degree.

2. Step 2: Combine to get total complexity

   Total time is proportional to number of nodes plus number of edges -> O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard BFS topological sort runs in linear time relative to graph size [OK]

Hint: Each edge and node processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing dense graph worst case with typical complexity
• Ignoring that BFS processes nodes once

3. What is the time complexity of the optimal approach using a single trust score array to find the town judge, given n people and m trust pairs?

medium

A. O(n * m) because we scan trust pairs for each person

B. O(n^2) because we check trust relationships pairwise

C. O(m^2) because trust pairs are nested in loops

D. O(n + m) because we process each trust pair once and then scan all people once

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates once over all trust pairs (m) and then once over all people (n).

2. Step 2: Combine complexities

   Processing trust pairs is O(m), scanning people is O(n), total O(n + m).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single pass over trust and people arrays [OK]

Hint: Single pass over trust pairs and people yields O(n + m) [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing trust pairs count with people count
• Ignoring linear scans after trust processing

4. What is the time complexity of the optimal BFS approach for the Pacific Atlantic Water Flow problem on an m x n grid, and why?

medium

A. O(m * n) because each cell is enqueued and processed at most once per ocean.

B. O(m * n * log(m * n)) due to priority queue operations in BFS.

C. O(m^2 * n^2) because BFS is run from every cell.

D. O(m + n) because BFS only processes border cells.

Solution

1. Step 1: Analyze BFS visits

   Each BFS starts from border cells and visits each cell at most once per ocean, so total visits ≤ 2 * m * n.

2. Step 2: Confirm no repeated work

   Visited arrays prevent revisiting cells, so BFS complexity is linear in number of cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each cell processed once per ocean -> O(m*n) [OK]

Hint: BFS visits each cell once per ocean [OK]

Common Mistakes:

• Confusing with brute force DFS from every cell
• Assuming BFS uses priority queue

5. Examine the following buggy code snippet for bidirectional BFS to find the shortest path in a binary matrix. Which line contains the subtle bug that can cause infinite loops or incorrect results?

def visit(queue, visited, other_visited):
    r, c = queue.popleft()
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
            if (nr, nc) in other_visited:
                return visited[(r, c)] + other_visited[(nr, nc)]
            if (nr, nc) not in visited:
                queue.append((nr, nc))  # Bug here
                # Missing visited marking here
    return None

medium

A. Line where the current cell is popped from the queue

B. Line where the cell is checked if in other_visited

C. Line where neighbors are checked for grid boundaries

D. Line where neighbor is appended to queue without marking visited

Solution

1. Step 1: Identify visited marking usage

   Visited must be marked when neighbor is enqueued to avoid revisiting.

2. Step 2: Locate missing visited marking

   Neighbor is appended to queue but not marked visited, causing possible infinite revisits.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Marking visited on enqueue prevents infinite loops [OK]

Hint: Mark visited when enqueuing neighbors [OK]

Common Mistakes:

• Mark visited only when dequeuing
• Forgetting visited marking entirely