Minimum Number of Vertices to Reach All Nodes

How it works

We do not need to store the actual source vertices for each destination. We only care whether a vertex has at least one incoming edge. A simple boolean array is sufficient: mark each destination as having an incoming edge, then return all vertices that were never marked.

Steps

1. Create a boolean array indegree of size n, initialized to false.
2. For each edge (src, dst), set indegree[dst] = true.
3. Collect all vertices i where indegree[i] is false.
4. Return these vertices as res.

Complexity

• Time complexity: O(V + E)
• Space complexity: O(V)

Where V is the number of vertices and E is the number of edges.

Things to watch for

Tracking Outgoing Edges Instead of Incoming

The problem asks for nodes that cannot be reached from other nodes, which means nodes with zero incoming edges. Tracking outgoing edges instead will identify nodes that cannot reach others, which is the opposite of what is needed.

Overcomplicating With Graph Traversal

Since the graph is acyclic and we only need nodes with no incoming edges, a simple pass through the edges is sufficient. Implementing full DFS or BFS adds unnecessary complexity and potential for bugs when a simple indegree check solves the problem optimally.

from typing import List

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        indegree = [False] * n
        for src, dst in edges:
            indegree[dst] = True
        return [i for i in range(n) if not indegree[i]]

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<bool> indegree(n, false);
        for (const auto& edge : edges) {
            indegree[edge[1]] = true;
        }

        vector<int> res;
        for (int i = 0; i < n; i++) {
            if (!indegree[i]) {
                res.push_back(i);
            }
        }
        return res;
    }
};