Minimum Number of Vertices to Reach All Nodes

This problem requires identifying the minimum number of starting vertices needed to reach all nodes in a directed acyclic graph, which can be efficiently solved by analyzing node in-degrees and applying topological sorting techniques.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we assume that the input is a directed acyclic graph (DAG), or could it contain cycles?
2. What's the expected range of node values? Are they guaranteed to be in the range [0, n-1]?
3. Should we return the vertices in any specific order, or is any valid ordering acceptable?
4. Can we modify the input graph structure, or must we work with a copy?
5. What's the target time complexity for the solution? Are we aiming for O(n + m) where n is nodes and m is edges?

Restatement in my own words: Given a directed graph with n nodes and a list of directed edges, we need to find the minimum number of starting vertices from which we can reach all nodes in the graph. This is essentially asking for the minimum number of "root" nodes that can traverse the entire graph.

Problem constraints:

• Input is a directed graph with n nodes (numbered 0 to n-1)
• Edges are given as a list of [from, to] pairs
• We want the minimal set of starting nodes such that from these nodes, we can reach all other nodes
• The graph may contain cycles

Assumptions I'm making:

1. Nodes are numbered from 0 to n-1
2. The graph is not necessarily connected but might have multiple components
3. We can modify the input structure if needed (for optimization)
4. The graph is valid - no self-loops or invalid edge references

Data shape and hidden structure: The problem involves a directed graph where each node has an in-degree (number of incoming edges). The key insight is that nodes with zero in-degree are "sources" - they cannot be reached from any other node, so they must be included in our starting set. The minimum number of vertices needed is equal to the count of nodes with zero in-degree.

This problem has a hidden structure where we're essentially looking for the "root" components of the graph's strongly connected components or more precisely, identifying nodes that have no incoming edges - these are the only nodes that cannot be reached from any other node in the graph.

2. Pattern Recognition

The problem asks for the minimum number of vertices from which all nodes in a directed acyclic graph (DAG) can be reached. This is fundamentally about identifying the "root" or "source" nodes in a DAG.

Most likely pattern: Topological sorting and graph traversal with in-degree analysis

Wording that signals the pattern:

• "Reach all nodes" - This suggests we need to find starting points that can traverse the entire graph
• "Minimum number of vertices" - Indicates we want to minimize our starting set, which is a classic optimization problem
• "Directed acyclic graph" - The structure implies we can use topological ordering concepts

Why this problem fits the pattern: The key insight is that in a DAG, any node with in-degree 0 cannot be reached from any other node. These nodes must be included in our starting set because they have no incoming edges and thus serve as the true "sources" or roots of the graph's connected components.

Core insight needed to solve it: In a DAG, we only need to start from nodes with in-degree 0. Any node that has incoming edges can be reached from some other node, so we don't need to include it in our starting set. The minimum number of vertices needed is simply the count of nodes with in-degree 0.

This pattern is a variant of finding the minimum set of root nodes in a directed graph, which can be solved efficiently using in-degree counting rather than full graph traversal.

3. Approach Evolution

My first instinct is to think about this as a graph traversal problem where I need to find the minimum set of starting nodes that can reach all other nodes. But that's O(n²) in the worst case because for each potential starting node, I'd have to do a full traversal to see if it can reach everything. Let me think about how to optimize this by looking at the graph structure more carefully.

I notice that if I think about the in-degrees of nodes, there's a key insight here. In a directed graph, any node with in-degree 0 cannot be reached from any other node, so it must be one of our starting vertices. But I need to think more systematically about what happens with nodes that do have incoming edges.

Let me trace through the logic: if a node has in-degree > 0, it means there's at least one edge pointing to it from another node. This means that node can be reached from somewhere else in the graph, so it doesn't need to be one of our starting vertices. However, nodes with in-degree 0 have no incoming edges and thus cannot be reached from any other node, so they must be included in our starting set.

The key insight is that the minimum number of vertices needed equals the count of nodes with in-degree 0. This is because:

1. Any node with in-degree 0 cannot be reached from any other node, so it must be a starting point
2. Any node with in-degree > 0 can be reached from some other node, so it doesn't need to be a starting point
3. The minimum set of vertices that can reach all nodes is exactly the set of nodes with in-degree 0

This reduces the problem from O(n²) graph traversal to O(n + m) where m is the number of edges, by simply counting in-degrees.

The approach I'll use:

1. Calculate in-degree for each node
2. Count how many nodes have in-degree 0
3. Return that count

This is optimal because we must examine each edge at least once to determine in-degrees, and we must return the count of nodes with zero in-degree.

Important invariant: The set of nodes with in-degree 0 forms a minimal vertex cover for reachability in the directed graph. Any node that can be reached from another node doesn't need to be in our starting set, but any node with no incoming edges must be included.

4. Data Structure Choice

For this problem, I need to identify the minimum set of vertices from which all nodes in a directed graph are reachable. The key insight is that these "source" vertices are those with zero in-degree, since they have no incoming edges and thus cannot be reached from any other node.

Primary Data Structures:

1. Array/HashMap for In-degree Tracking: I'll use an array or HashMap to track the in-degree of each node. This is essential because:

   • It allows O(1) lookup and update operations
   • It's the most efficient way to count incoming edges for each node
   • Space complexity is O(V) where V is the number of vertices

2. List/ArrayList for Result Collection: I'll collect the zero in-degree nodes in a list:

   • Simple and efficient for this use case
   • Allows easy conversion to required return format (array or list)
   • Space complexity is O(K) where K is the number of source vertices

Why These Choices Are Optimal:

The array-based approach works perfectly when node IDs are in the range [0, n-1], making it O(1) access time. If node IDs were sparse or arbitrary, a HashMap would be more appropriate but with O(1) average case access time.

The list structure is ideal for collecting the final answer since:

• It's the natural container for a variable-size result set
• It avoids unnecessary sorting or complex data structure overhead
• It's easy to convert to the required return format

Helper Structures:

No additional helper structures are needed beyond what's described above. The solution only requires tracking in-degrees and collecting nodes with zero in-degree, which can be done with simple counting and filtering operations.

This approach avoids complex graph traversal or cycle detection algorithms that would be overkill for this specific problem structure. The solution directly leverages the mathematical property that nodes with zero in-degree form the minimal set of sources needed to reach all nodes in a DAG.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works.

Consider input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]

Step 1: Initialize data structures

• inDegree array: [0, 1, 2, 0, 1, 1] (indices 0-5)
• result list: []

Step 2: Calculate in-degrees Processing each edge:

• 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 3: Find nodes with zero in-degree Iterating through nodes 0 to 5:

• Node 0: inDegree[0] = 0 → add to result
• Node 1: inDegree[1] = 1 → skip
• Node 2: inDegree[2] = 2 → skip
• Node 3: inDegree[3] = 0 → add to result
• Node 4: inDegree[4] = 1 → skip
• Node 5: inDegree[5] = 1 → skip

Step 4: Return result Result list contains [0,3]

Why this works: Nodes with zero in-degree are those that cannot be reached from any other node, so they must be starting points. Any node with in-degree > 0 can be reached from some other node, so it's not a required starting point. The algorithm correctly identifies all nodes that must be included in our minimum set.

Edge case handling: If input had only one node with no edges, we'd return [0]. If all nodes had in-degree > 0, we'd return an empty list (but that would mean the graph has cycles, which contradicts the problem constraints).

public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
    int[] inDegree = new int[n];
    
    // Calculate in-degrees for each node
    for (List<Integer> edge : edges) {
        int to = edge.get(1);
        inDegree[to]++;
    }
    
    // Collect all nodes with zero in-degree
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            result.add(i);
        }
    }
    
    return result;
}

6. Java Solution

import java.util.*;

public class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        // Step 1: Identify nodes with in-degree 0
        // These nodes cannot be reached from any other node
        int[] inDegree = new int[n];
        
        // Calculate in-degree for each node
        for (List<Integer> edge : edges) {
            int to = edge.get(1);
            inDegree[to]++;
        }
        
        // Step 2: Collect all nodes with in-degree 0
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                result.add(i);
            }
        }
        
        return result;
    }
}

This solution works by recognizing that in a directed acyclic graph (DAG), nodes with zero in-degree are exactly those that cannot be reached from any other node. These nodes must be included in our answer set since they serve as starting points for reaching all other nodes. The approach efficiently identifies these nodes in linear time by computing in-degrees and filtering for zero values.

7. Complexity Analysis

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.

The algorithm performs two main operations:

1. First pass through all edges to calculate in-degrees: O(E)
2. Second pass through all vertices to count nodes with zero in-degree: O(V)

Since we're processing each edge once and each vertex once, the total time complexity is O(E + V).

Space Complexity: O(V) for storing the in-degree array of size V.

The space usage is dominated by the in-degree tracking array, which requires one integer per vertex. No additional data structures scale with input size beyond this.

Why these bounds are correct:

• Each edge is visited exactly once in the first loop
• Each vertex is checked exactly once in the second loop
• The in-degree array size is directly proportional to the number of vertices
• No nested loops or recursive calls that would increase complexity

Optimality: This solution is optimal for the problem as stated. Since we must examine each edge to determine in-degrees and each vertex to identify those with zero in-degree, we cannot do better than O(V + E). The solution achieves the theoretical lower bound for this graph problem.

The algorithm is linear in both time and space, making it highly efficient for large graphs. The approach avoids any sorting or searching operations that would increase complexity beyond linear time.

8. Edge Cases & Pitfalls

Edge cases that must be handled:

• Empty graph: If n = 0, return empty list. If n = 1 with no edges, return [0].
• Single node: If n = 1, return [0] regardless of edges.
• Disconnected components: Multiple disconnected subgraphs require multiple starting vertices.
• Self-loops and cycles: These don't change the fundamental approach but must be handled correctly in edge counting.
• Duplicate edges: Should be ignored as they don't change reachability.

Common implementation pitfalls:

1. Incorrect in-degree calculation: Failing to properly count incoming edges for each node.
2. Misunderstanding the problem: Thinking we need to find a single path that visits all nodes, rather than identifying minimum starting points.
3. Not handling zero in-degree correctly: Nodes with zero in-degree are exactly the ones that can serve as starting points.
4. Indexing errors: Using 1-based indexing when the problem uses 0-based node IDs.
5. Overcomplicating with DFS/BFS: While these work, they're unnecessary when the mathematical insight of in-degrees suffices.

The key insight is that we only need to count nodes with zero in-degree, which naturally handles all these edge cases without additional complexity.

9. Alternative Approaches

There are several alternative approaches to solving this problem, each with different trade-offs:

1. Reverse Graph Approach with DFS Instead of counting in-degrees, we can build a reverse graph and perform DFS from all nodes to find which nodes cannot be reached from any other node. This approach would involve:

• Building a reverse adjacency list
• Performing DFS from each node to mark reachable nodes
• Counting nodes that are never marked as reachable from others

This is less efficient with O(V + E) time complexity but requires more complex graph traversal logic.

2. Set-based Approach We can use a set to track all nodes that have incoming edges:

Set<Integer> hasIncoming = new HashSet<>();
for (int[] edge : edges) {
    hasIncoming.add(edge[1]);
}

Then return all nodes not in this set. This is essentially the same as our in-degree counting but with a different data structure.

3. Union-Find Approach We could use Union-Find to detect connected components, but this is overkill for the problem since we only need to identify root nodes in a directed acyclic graph, not connected components in a general graph.

4. Topological Sort Approach We could perform topological sorting and return nodes with in-degree 0, but this is more complex than necessary since we only care about the count of nodes with zero in-degree.

The original approach is preferred because it's the most direct, readable, and efficient solution that directly addresses what we're trying to find: nodes with in-degree zero. The alternatives either add unnecessary complexity or have higher constant factors without providing meaningful benefits for this specific problem.

The in-degree counting approach is optimal because it directly answers the question without requiring complex graph traversals or additional data structure management.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic example from problem description
        // Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
        // Expected: [0,3]
        int n1 = 6;
        int[][] edges1 = {{0,1},{0,2},{2,5},{3,4},{4,2}};
        // Should return [0,3] - nodes 0 and 3 have no incoming edges
        
        // Test Case 2: Single node with no edges
        int n2 = 1;
        int[][] edges2 = {};
        // Expected: [0]
        
        // Test Case 3: All nodes form a single path
        int n3 = 4;
        int[][] edges3 = {{0,1},{1,2},{2,3}};
        // Expected: [0] - only node 0 has no incoming edges
        
        // Test Case 4: Multiple disconnected components
        int n4 = 5;
        int[][] edges4 = {{0,1},{2,3}};
        // Expected: [0,2] - nodes 0 and 2 have no incoming edges
        
        // Test Case 5: Cycle in graph
        int n5 = 3;
        int[][] edges5 = {{0,1},{1,2},{2,0}};
        // Expected: [] - all nodes have incoming edges
        
        // Test Case 6: Complex graph with multiple sources
        int n6 = 8;
        int[][] edges6 = {{0,1},{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{0,7}};
        // Expected: [0] - only node 0 has no incoming edges
        
        // Test Case 7: All nodes have incoming edges except one
        int n7 = 4;
        int[][] edges7 = {{1,0},{2,0},{3,0}};
        // Expected: [0] - only node 0 has no incoming edges
    }
}

Representative Test Cases:

1. Basic Example: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] → Expected: [0,3]

   • Covers the typical case with multiple sources

2. Single Node: n = 1, edges = [] → Expected: [0]

   • Edge case with minimal input

3. Linear Path: n = 4, edges = [[0,1],[1,2],[2,3]] → Expected: [0]

   • Tests simple path with one source

4. Disconnected Components: n = 5, edges = [[0,1],[2,3]] → Expected: [0,2]

   • Validates handling of multiple independent sources

5. Cycle Detection: n = 3, edges = [[0,1],[1,2],[2,0]] → Expected: []

   • Tests case where all nodes have incoming edges

Tricky Case:

Multiple Sources with Complex Dependencies: n = 8, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[0,7]] → Expected: [0]

• This tests that we correctly identify only the root nodes with zero in-degree

Boundary Case:

All Nodes Have In-edges: n = 4, edges = [[1,0],[2,0],[3,0]] → Expected: [0]

• Validates that we properly handle the case where all nodes except one have incoming edges

These test cases cover various graph topologies including linear chains, disconnected components, cycles, and edge conditions that can reveal implementation bugs or incorrect assumptions about the problem requirements.

11. Final Summary

The core insight is that nodes with zero in-degree are the only ones that cannot be reached from any other node, so we must include all such nodes in our starting set. This greedy approach is optimal because each node with zero in-degree must be visited at least once to ensure reachability.

The solution works by counting in-degrees for all nodes, then collecting those with zero in-degree. This is optimal because:

• We make exactly one pass through edges to compute in-degrees (O(E))
• We make one pass through all nodes to find those with zero in-degree (O(V))
• Space usage is O(V) for the in-degree array
• The solution is mathematically proven to be minimal since any node with in-degree zero must be included

This approach is more efficient than alternatives like DFS/BFS traversal or topological sorting, which would require additional graph traversals and are unnecessarily complex for this specific problem structure.