1557. Minimum Number of Vertices to Reach all Nodes - Explanation

1. Depth First Search

Intuition

We want to find the smallest set of vertices from which all other vertices are reachable. A vertex must be in this set if no other vertex can reach it, meaning it has no incoming edges.

Using dfs, we traverse from each unvisited node and mark all reachable nodes. Any node that gets reached from another node can be removed from our candidate set. The nodes that remain are those with no incoming edges.

Algorithm

Build an adjacency list from the edges.
Initialize a set containing all vertices as potential starting points.
For each unvisited vertex, run dfs:
- Mark the vertex as visited.
- For each neighbor, recursively visit it and remove it from the res set.
Return the remaining vertices in the set.

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)

        res = set(range(n))
        visited = [False] * n

        def dfs(node):
            visited[node] = True
            for nei in adj[node]:
                if not visited[nei]:
                    dfs(nei)
                res.discard(nei)

        for i in range(n):
            if not visited[i]:
                dfs(i)
        return list(res)

Time & Space Complexity

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

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

2. Iterative DFS

Intuition

This is the same approach as recursive dfs but uses an explicit stack to avoid recursion. We process nodes iteratively, marking each visited node and removing any node that has an incoming edge from our candidate set.

Algorithm

Build an adjacency list from the edges.
Initialize a boolean array where all vertices are potential res.
Use a stack for iterative dfs:
- Pop a node from the stack.
- Skip if already visited; otherwise mark as visited.
- For each neighbor, add to stack if unvisited and mark as not a res.
Collect all vertices still marked as res.

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)

        res = [True] * n
        visited = [False] * n
        stack = []

        for i in range(n):
            if not visited[i]:
                stack.append(i)
                while stack:
                    node = stack.pop()
                    if visited[node]:
                        continue
                    visited[node] = True
                    for nei in adj[node]:
                        if not visited[nei]:
                            stack.append(nei)
                        res[nei] = False

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

Time & Space Complexity

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

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

3. Indegree Count

Intuition

A vertex needs to be in our starting set only if it cannot be reached from any other vertex. This happens exactly when the vertex has no incoming edges. We can track which vertices have incoming edges by building a list of sources for each destination.

Algorithm

Create an array of lists where incoming[v] stores all vertices with edges pointing to v.
Iterate through all edges and populate the incoming lists.
Collect all vertices where incoming[v] is empty.
Return these vertices as the res.

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        incoming = collections.defaultdict(list)
        for src, dst in edges:
            incoming[dst].append(src)

        res = []
        for i in range(n):
            if not incoming[i]:
                res.append(i)
        return res

Time & Space Complexity

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

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

4. Indegree Count (Optimal)

Intuition

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.

Algorithm

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

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]]

Time & Space Complexity

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

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

Common Pitfalls

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.