Minimum Number of Vertices to Reach All Nodes

Intuition

Think about which nodes we are forced to include. If a node has at least one incoming edge, then some other node points to it, so it is reachable without ever selecting it directly. That means we never need to include any node with a positive indegree. On the other hand, a node with indegree zero has no incoming edge at all, so nothing can reach it and it must be a starting point. Because the graph is acyclic, choosing all zero-indegree nodes is both necessary and sufficient to cover every node. So the whole problem reduces to counting incoming edges and returning the nodes that received none.

Algorithm walkthrough

1. 1Create an indegree array of size n, all zeros.
2. 2For every edge [a, b], increment indegree[b], since b has one more incoming edge.
3. 3Scan every node from 0 to n - 1.
4. 4Whenever a node's indegree is zero, add it to the answer because it cannot be reached from any other node.
5. 5Return the collected list of zero-indegree nodes.

Implementation

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        indegree = [0] * n
        for _, v in edges:
            indegree[v] += 1
        return [i for i in range(n) if indegree[i] == 0]