Minimum Number of Vertices to Reach All Nodes

📋

Problem

Imagine you want to send a message to every employee in a company, but you can only start by directly contacting a few key people. Who should you pick so that everyone eventually hears the message?

Given a directed acyclic graph (DAG) with n vertices labeled from 0 to n-1, and a list of edges where edges[i] = [from_i, to_i], find the minimum set of vertices from which all nodes in the graph are reachable. Return any such set of vertices.

1 ≤ n ≤ 10^51 ≤ edges.length ≤ 10^5edges[i].length == 20 ≤ from_i, to_i < nAll edges are uniqueThe graph is a DAG (no cycles)

Edge cases: Graph with no edges → all nodes must be chosenGraph where all nodes except one have incoming edges → only one node chosenGraph with multiple disconnected components → one zero in-degree node per component

</>

IDE

def findSmallestSetOfVertices(n: int, edges: list) -> list:public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges)vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges)function findSmallestSetOfVertices(n, edges)

def findSmallestSetOfVertices(n, edges):
    # Write your solution here
    pass

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    // Write your solution here
    return {};
}

function findSmallestSetOfVertices(n, edges) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,2]Selecting nodes with incoming edges instead of zero in-degree nodes.✅ Compute in-degree array and return all nodes with zero in-degree.

Wrong: []Returning empty list when graph has zero in-degree nodes (e.g., no edges or single node).✅ Return all nodes with zero in-degree, never empty if such nodes exist.

Wrong: [0,1,2,3,4]Returning all nodes regardless of in-degree, ignoring minimal set requirement.✅ Return only nodes with zero in-degree to minimize the set.

Wrong: TLE or timeoutUsing BFS/DFS from every node causing O(n*(n+e)) complexity.✅ Use in-degree counting to find zero in-degree nodes in O(n + e) time.

✓

Test Cases

Focus on boundary conditions like empty graphs and single nodes to solidify your base cases.

Watch out for common pitfalls like cycles and greedy selection of nodes.

Optimize your solution to linear time by leveraging in-degree counts instead of repeated BFS.

t1_01basic

Input{"n":6,"edges":[[0,1],[0,2],[2,5],[3,4],[4,2]]}

Expected[0,3]

⏱ Performance - must finish in 2000ms

Vertices 0 and 3 have zero in-degree and starting from them, all nodes can be reached.

💡 Focus on nodes with no incoming edges as starting points.

💡 Count in-degree of each node to identify zero in-degree nodes.

💡 Return all nodes with zero in-degree as the minimal set.

Why it failed: Returned set missing zero in-degree nodes or includes nodes with incoming edges; fix by selecting all nodes with zero in-degree exactly. This is the canonical basic case.

✓ Correctly identified all zero in-degree nodes as minimal starting vertices.

t1_02basic

Input{"n":5,"edges":[[0,1],[2,1],[3,4]]}

Expected[0,2,3]

⏱ Performance - must finish in 2000ms

Nodes 0, 2, and 3 have zero in-degree; all others have incoming edges.

💡 Check which nodes have no incoming edges.

💡 Nodes with zero in-degree form the minimal set to reach all nodes.

💡 Return all zero in-degree nodes: 0, 2, and 3.

Why it failed: Output missing one or more zero in-degree nodes or includes nodes with incoming edges; fix by computing in-degree and returning all zero in-degree nodes. This is a standard basic case.

✓ Correctly returned all zero in-degree nodes.

t2_01edge

Input{"n":4,"edges":[]}

Expected[0,1,2,3]

⏱ Performance - must finish in 2000ms

No edges means all nodes have zero in-degree; all must be chosen.

💡 Consider what happens when there are no edges.

💡 All nodes have zero in-degree in this case.

💡 Return all nodes as the minimal set.

Why it failed: Returned fewer nodes than total when no edges exist; fix by returning all nodes when in-degree is zero for all. This is the empty graph edge case.

✓ Correctly returned all nodes when graph has no edges.

t2_02edge

Input{"n":1,"edges":[]}

Expected[0]

⏱ Performance - must finish in 2000ms

Single node with no edges must be chosen.

💡 Check the smallest graph possible.

💡 Single node has zero in-degree by default.

💡 Return the single node as the minimal set.

Why it failed: Returned empty set for single node graph; fix by returning node 0 when n=1. This is the single node edge case.

✓ Correctly returned the single node as minimal set.

t2_03edge

Input{"n":3,"edges":[[0,1],[1,2]]}

Expected[0]

⏱ Performance - must finish in 2000ms

Only node 0 has zero in-degree; it can reach all nodes.

💡 Identify nodes with zero in-degree.

💡 Only node 0 has zero in-degree here.

💡 Return node 0 as the minimal set.

Why it failed: Returned multiple nodes or missed node 0; fix by selecting all zero in-degree nodes exactly. This is the exact boundary edge case.

✓ Correctly returned the single zero in-degree node.

t3_01corner

Input{"n":5,"edges":[[0,1],[1,2],[2,3],[3,4],[4,1]]}

Expected[0]

⏱ Performance - must finish in 2000ms

Graph contains a cycle (1->2->3->4->1), but problem states DAG; here no zero in-degree nodes exist.

💡 Check if graph is truly a DAG.

💡 If no zero in-degree nodes, minimal set is empty or invalid.

💡 Return empty list if no zero in-degree nodes found.

Why it failed: Returned non-empty set despite no zero in-degree nodes; fix by returning empty list when no zero in-degree nodes exist. This is the cycle detection corner case.

✓ Correctly returned empty list when no zero in-degree nodes exist.

t3_02corner

Input{"n":6,"edges":[[0,1],[1,2],[2,3],[3,4],[4,5]]}

Expected[0]

⏱ Performance - must finish in 2000ms

Only node 0 has zero in-degree; all nodes reachable from it.

💡 Check if greedy approach picking any node works.

💡 Only zero in-degree nodes can start full reach.

💡 Return node 0 as minimal set.

Why it failed: Returned multiple nodes or nodes with incoming edges; fix by selecting all zero in-degree nodes only. This is the greedy trap corner case.

✓ Correctly returned the single zero in-degree node.

t3_03corner

Input{"n":4,"edges":[[0,1],[1,2],[2,3],[0,3]]}

Expected[0]

⏱ Performance - must finish in 2000ms

Node 0 has zero in-degree and can reach all nodes; no other zero in-degree nodes.

💡 Check if multiple paths affect zero in-degree nodes.

💡 Only nodes with zero in-degree matter for minimal set.

💡 Return node 0 as minimal set.

Why it failed: Returned nodes with incoming edges or multiple nodes; fix by returning only zero in-degree nodes. This is the multiple paths corner case.

✓ Correctly returned the zero in-degree node.

t4_01performance

Input{"n":100000,"edges":[]}

Expectednull

⏱ Performance - must finish in 2000ms

Graph with 100000 nodes and no edges; O(n + e) solution must complete within 2 seconds.

💡 Use in-degree counting for O(n + e) complexity.

💡 Avoid BFS/DFS from every node to prevent TLE.

💡 Return all nodes with zero in-degree efficiently.

Why it failed: TLE due to brute force BFS from every node; fix by using in-degree counting approach. This is the O(n*(n+e)) complexity TLE case.

✓ Efficient O(n + e) solution confirmed by passing performance test.

Practice

1. You are given a grid representing water and land cells. The task is to find the water cell that is farthest from any land cell, maximizing the shortest distance to land. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Run a DFS from each water cell to find the nearest land cell and pick the maximum distance found.

B. Perform a multi-source BFS starting simultaneously from all land cells to compute the shortest distance to water cells.

C. Use a greedy approach that picks the water cell farthest from the first land cell found.

D. Apply dynamic programming to store distances from land cells and update iteratively.

Solution

1. Step 1: Understand the problem requires shortest distance from any land cell to water cells.

   DFS from each water cell is inefficient and does not guarantee shortest path globally.

2. Step 2: Multi-source BFS from all land cells simultaneously propagates shortest distances correctly.

   This approach ensures all water cells get the minimum distance to any land cell in O(n^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Multi-source BFS finds shortest paths from multiple sources efficiently [OK]

Hint: Multi-source BFS finds shortest distances from all land cells [OK]

Common Mistakes:

• Using DFS for shortest path leads to incorrect distances
• Greedy approach ignores other land cells
• Dynamic programming is not straightforward here

2. Consider the following Python code implementing flood fill using DFS. Given the input image = [[1,1,1],[1,1,0],[1,0,1]], starting pixel (sr=1, sc=1), and newColor=2, what is the final image returned?

easy

A. [[1,1,1],[1,2,0],[1,0,1]]

B. [[2,2,2],[2,2,0],[2,0,2]]

C. [[2,2,2],[2,2,0],[2,0,1]]

D. [[2,2,2],[2,2,2],[2,2,2]]

Solution

1. Step 1: Trace dfs starting at (1,1) with original color=1

   The pixel at (1,1) is recolored to 2. Its neighbors with color 1 are (0,1), (2,1) is 0 so skipped, (1,0), and (1,2) is 0 skipped.

2. Step 2: Recursively recolor connected pixels with color 1

   All connected pixels with color 1 reachable from (1,1) are recolored to 2, resulting in [[2,2,2],[2,2,0],[2,0,1]]. The pixel at (2,2) remains 1 as it is not connected 4-directionally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only connected pixels with original color changed [OK]

Hint: Trace DFS calls carefully to find connected pixels [OK]

Common Mistakes:

• Changing pixels diagonally connected
• Forgetting to check boundaries

3. Consider the following code snippet for the Keys and Rooms problem:

def canVisitAllRooms(rooms):
    n = len(rooms)
    visited = [false] * n
    count = 0
    def dfs(room):
        nonlocal count
        if visited[room]:
            return
        visited[room] = true
        count += 1
        if count == n:
            return
        for key in rooms[room]:
            dfs(key)
    dfs(0)
    return count == n

rooms = [[1], [2], [3], []]
print(canVisitAllRooms(rooms))

What is the value of count after the DFS call completes?

easy

A. 3

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace DFS calls starting from room 0

   Visit room 0 (count=1), then room 1 (count=2), then room 2 (count=3), then room 3 (count=4).

2. Step 2: Confirm all rooms visited

   Since count equals total rooms (4), DFS stops early and returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All rooms reachable, count matches number of rooms [OK]

Hint: Count increments once per unique room visited [OK]

Common Mistakes:

• Off-by-one error counting rooms
• Assuming count stops at 3 instead of 4
• Confusing count with length of visited list

4. You are given a 2D grid containing 'X' and 'O'. The goal is to flip all 'O's that are completely surrounded by 'X's into 'X's themselves, but keep 'O's connected to the boundary unchanged. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Use a brute force approach checking each 'O' region independently with DFS to see if it touches the boundary.

B. Mark all 'O's connected to the boundary first using BFS or DFS, then flip the rest of the 'O's to 'X'.

C. Apply dynamic programming to store subproblems of surrounded regions and combine results.

D. Use a greedy approach to flip 'O's as soon as they are found surrounded by 'X's.

Solution

1. Step 1: Understand the problem constraints

   The problem requires flipping only those 'O's that are fully surrounded by 'X's, meaning 'O's connected to the boundary must remain unchanged.

2. Step 2: Identify the correct approach

   Marking all 'O's connected to the boundary first ensures these safe regions are preserved. Then flipping the rest is straightforward. This approach is efficient and guarantees correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Boundary-connected marking prevents flipping safe 'O's [OK]

Hint: Mark boundary-connected 'O's first to preserve them [OK]

Common Mistakes:

• Trying to check each 'O' region independently leads to high complexity.
• Using greedy flips misses connected 'O's that should be preserved.
• Dynamic programming is not suitable for connectivity problems on grids.

5. Suppose the graph edges can have negative weights but no negative cycles. Which algorithm modification or choice correctly computes the shortest network delay times from a start node?

hard

A. Use DFS with path relaxation and memoization to handle negative weights efficiently.

B. Use Dijkstra's algorithm with a priority queue as usual; it handles negative weights correctly.

C. Use BFS since negative weights can be ignored for shortest paths.

D. Use Bellman-Ford algorithm to relax edges repeatedly, detecting negative cycles if any.

Solution

1. Step 1: Recognize that Dijkstra's algorithm fails with negative weights because it assumes non-negative edge costs

   BFS cannot handle weighted edges properly, and DFS with memoization is inefficient and may not terminate correctly.

2. Step 2: Bellman-Ford algorithm is designed to handle negative weights and detect negative cycles by repeated edge relaxation

   It guarantees correct shortest paths if no negative cycles exist.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bellman-Ford handles negative weights safely [OK]

Hint: Bellman-Ford handles negative weights; Dijkstra does not [OK]

Common Mistakes:

• Using Dijkstra with negative weights incorrectly
• Assuming BFS works for weighted graphs
• Believing DFS with memoization is efficient here