Code Implementation

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

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> indegree(n, 0);
        for (auto& edge : edges) {
            indegree[edge[1]]++;
        }
        vector<int> res;
        for (int i = 0; i < n; ++i) {
            if (indegree[i] == 0) res.push_back(i);
        }
        return res;
    }
};
      

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        int[] indegree = new int[n];
        for (List<Integer> edge : edges) {
            indegree[edge.get(1)]++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (indegree[i] == 0) res.add(i);
        }
        return res;
    }
}
      

var findSmallestSetOfVertices = function(n, edges) {
    const indegree = Array(n).fill(0);
    for (const [u, v] of edges) {
        indegree[v]++;
    }
    const res = [];
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) res.push(i);
    }
    return res;
};
      

Problem Description

You are given a directed graph with n nodes, labeled from 0 to n-1, and a list of directed edges edges where each edge is represented as [from, to]. Your task is to find the minimum number of vertices from which all nodes in the graph are reachable by following the edges. You should return a list of these vertices. Each vertex can only be used once, and there is always at least one valid solution.

• Each edge is directed from from to to.
• Do not reuse elements in your answer.
• Return the answer in any order.

Thought Process

At first glance, it may seem like we need to explore all possible sets of starting vertices and check which ones can reach every node, but this would be very inefficient. Instead, we should look for a property or shortcut that allows us to determine the minimum set efficiently.

In a directed graph, a node that has no incoming edges cannot be reached from any other node. Therefore, to reach that node, we must include it as a starting point. Nodes with incoming edges, however, might be reached from other nodes, so we may not need to start from them.

This insight suggests that the answer is simply all nodes with zero indegree (i.e., no incoming edges). Any node with at least one incoming edge can be reached from somewhere else, so we do not need to include it in our starting set.

Solution Approach

• Step 1: Initialize an array (or similar structure) to keep track of the indegree (number of incoming edges) for each node.
• Step 2: Iterate through the edges list. For each edge [from, to], increment the indegree of to by 1.
• Step 3: After processing all edges, scan through the indegree array. For each node with indegree zero, add it to the result list. These are the nodes that cannot be reached from any other node and so must be included as starting points.
• Step 4: Return the result list. The order does not matter.

We use an array for indegree counts because array lookups and updates are O(1), making the solution efficient.

Example Walkthrough

Let's use the following example:

• n = 6
• edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]

Step 1: Compute indegrees

• Start with indegree = [0,0,0,0,0,0]
• Edge [0,1]: indegree[1] += 1 → [0,1,0,0,0,0]
• Edge [0,2]: indegree[2] += 1 → [0,1,1,0,0,0]
• Edge [2,5]: indegree[5] += 1 → [0,1,1,0,0,1]
• Edge [3,4]: indegree[4] += 1 → [0,1,1,0,1,1]
• Edge [4,2]: indegree[2] += 1 → [0,1,2,0,1,1]

Step 2: Collect nodes with indegree 0

• Node 0: indegree 0 → include in result
• Node 1: indegree 1 → skip
• Node 2: indegree 2 → skip
• Node 3: indegree 0 → include in result
• Node 4: indegree 1 → skip
• Node 5: indegree 1 → skip

This means that starting from nodes 0 and 3, we can reach every node in the graph.

Time and Space Complexity

Brute-force approach: Try all subsets of nodes as starting points and check if all nodes are reachable. This is exponential in n: O(2^n * (n + m)), where m is the number of edges. It's not feasible for large graphs.

Optimized approach (current solution):

• Time Complexity: O(n + m). We process each edge once to compute indegrees (O(m)), and then scan the indegree array once (O(n)).
• Space Complexity: O(n). We use an array of size n to store indegrees, and the output list is at most size n.

Summary

The key insight is that only nodes with zero indegree need to be included as starting points to reach all nodes in a directed graph. By counting indegrees, we quickly identify these nodes. This leads to an elegant and efficient O(n + m) solution, avoiding the need for expensive graph traversals or subset checks.