Problem Description

You are given a directed acyclic graph (DAG) with n vertices labeled from 0 to n-1. The graph is represented by an array edges where each element edges[i] = [from_i, to_i] indicates a directed edge from vertex from_i to vertex to_i.

Your task is to find the smallest set of vertices such that starting from these vertices, you can reach every vertex in the graph. The problem guarantees that there is exactly one unique solution.

The key insight is that in a directed graph, a vertex needs to be in the starting set if and only if it has no incoming edges. This is because:

• If a vertex has incoming edges, it can be reached from other vertices, so it doesn't need to be a starting point
• If a vertex has no incoming edges (in-degree of 0), there's no way to reach it from other vertices, so it must be included in the starting set

The solution counts the incoming edges for each vertex using a Counter. Any vertex i that has zero incoming edges (cnt[i] == 0) must be part of the minimum starting set. These vertices with no predecessors form the smallest set from which all other vertices can be reached through the directed edges.

For example, if you have edges [[0,1], [0,2], [2,3], [3,4]], vertices 1, 2, 3, and 4 all have incoming edges, but vertex 0 has none. Therefore, the answer would be [0] since starting from vertex 0, you can reach all other vertices in the graph.

Intuition

To understand why we need to find vertices with no incoming edges, let's think about the problem step by step.

First, consider what it means for a vertex to be reachable. In a directed graph, vertex B is reachable from vertex A if there's a path of directed edges from A to B. Now, if we want to reach all vertices in the graph, we need to carefully choose our starting points.

Think about it this way: if a vertex has an incoming edge, it means some other vertex points to it. This tells us that we can reach this vertex from somewhere else in the graph. So, we don't necessarily need to start from this vertex - we can reach it by starting from its predecessor.

On the other hand, what about vertices with no incoming edges? These vertices are special because there's no way to reach them from any other vertex in the graph. They are "source" vertices that can only serve as starting points, never as destinations from other vertices.

Here's the key realization: since the graph is acyclic (no cycles), if we don't include a vertex with no incoming edges in our starting set, we can never reach it at all! There's no path leading to it from any other vertex.

Therefore, the minimum set of starting vertices must include all vertices with in-degree 0 (no incoming edges). Moreover, this set is also sufficient because:

1. Every vertex with incoming edges can be reached from some vertex with fewer incoming edges
2. Following this chain backwards in the DAG, we eventually reach a vertex with no incoming edges
3. Since we include all such vertices in our starting set, every vertex in the graph becomes reachable

This leads us to the elegant solution: count the incoming edges for each vertex, and return all vertices that have zero incoming edges. These vertices form the unique smallest set from which all nodes are reachable.

Learn more about Graph patterns.

Solution Approach

The implementation is remarkably concise and leverages Python's built-in data structures to efficiently solve the problem.

Step 1: Count Incoming Edges

The solution uses Python's Counter from the collections module to count the incoming edges for each vertex:

cnt = Counter(t for _, t in edges)

This line deserves careful examination:

• edges contains pairs [from, to] representing directed edges
• The expression (t for _, t in edges) creates a generator that extracts only the destination vertices (to) from each edge
• The underscore _ is used as a placeholder for the source vertex since we don't need it
• Counter then counts how many times each destination vertex appears, giving us the in-degree of each vertex

For example, if edges = [[0,1], [0,2], [2,1]]:

• Vertex 1 appears as a destination twice (in-degree = 2)
• Vertex 2 appears as a destination once (in-degree = 1)
• Vertex 0 never appears as a destination (in-degree = 0)
• The Counter would be: {1: 2, 2: 1}

Step 2: Identify Vertices with Zero In-degree

return [i for i in range(n) if cnt[i] == 0]

This list comprehension:

• Iterates through all vertices from 0 to n-1
• Checks if each vertex i has an in-degree of 0 using cnt[i] == 0
• Note that if vertex i never appeared as a destination in the edges, cnt[i] returns 0 by default (Counter's behavior for missing keys)
• Collects all vertices with zero incoming edges into the result list

Time and Space Complexity:

• Time Complexity: O(E + V) where E is the number of edges and V is the number of vertices. We iterate through all edges once to build the counter, then through all vertices once to find those with zero in-degree.
• Space Complexity: O(V) for storing the counter, which in the worst case could have entries for all vertices.

The beauty of this solution lies in its simplicity - by identifying that vertices with no incoming edges must be in the minimum starting set, we reduce the problem to a simple counting exercise.

Example Walkthrough

Let's walk through a concrete example to see how the solution works.

Example Graph:

• n = 6 vertices (labeled 0 to 5)
• edges = [[0,1], [0,3], [2,3], [2,4], [3,4], [3,5]]

Step 1: Visualize the Graph

    0 → 1
    ↓
    3 → 4
    ↑   ↓
    2 → 5

Step 2: Count Incoming Edges

We iterate through each edge and count how many times each vertex appears as a destination:

• Edge [0,1]: vertex 1 is a destination
• Edge [0,3]: vertex 3 is a destination
• Edge [2,3]: vertex 3 is a destination (now count = 2)
• Edge [2,4]: vertex 4 is a destination
• Edge [3,4]: vertex 4 is a destination (now count = 2)
• Edge [3,5]: vertex 5 is a destination

Our counter becomes: {1: 1, 3: 2, 4: 2, 5: 1}

Step 3: Identify Vertices with Zero In-degree

Now we check each vertex from 0 to 5:

• Vertex 0: cnt[0] = 0 (not in counter, defaults to 0) ✓ Include
• Vertex 1: cnt[1] = 1 (has incoming edge from 0) ✗ Skip
• Vertex 2: cnt[2] = 0 (not in counter, no incoming edges) ✓ Include
• Vertex 3: cnt[3] = 2 (has incoming edges from 0 and 2) ✗ Skip
• Vertex 4: cnt[4] = 2 (has incoming edges from 2 and 3) ✗ Skip
• Vertex 5: cnt[5] = 1 (has incoming edge from 3) ✗ Skip

Result: [0, 2]

Verification: Starting from vertices 0 and 2, we can indeed reach all vertices:

• From 0: we can reach 1 and 3, and from 3 we can reach 4 and 5
• From 2: we can reach 3 and 4, and from 3 we can reach 5

This is the minimum set because if we excluded either 0 or 2, we wouldn't be able to reach all vertices (vertex 0 has no way to be reached except as a starting point, same for vertex 2).

Solution Implementation

Time and Space Complexity

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

• Creating the Counter object requires iterating through all edges once to extract target vertices: O(E)
• The list comprehension iterates through all vertices from 0 to n-1 to check which ones have zero incoming edges: O(N)
• Dictionary lookup for cnt[i] is O(1) on average
• Total: O(E) + O(N) = O(E + N)

Space Complexity: O(N) where N is the number of vertices.

• The Counter object cnt stores at most N unique vertices (in the worst case, every vertex except one has at least one incoming edge): O(N)
• The output list contains vertices with no incoming edges, which in the worst case could be O(N) vertices
• Total auxiliary space: O(N)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Counter's Default Behavior

A common mistake is assuming you need to explicitly initialize all vertices in the Counter before checking their in-degrees. Some developers might write unnecessary initialization code:

# Unnecessary initialization - DON'T DO THIS
in_degree_count = Counter()
for i in range(n):
    in_degree_count[i] = 0  # Redundant!
for source, destination in edges:
    in_degree_count[destination] += 1

Why it's a pitfall: Python's Counter returns 0 for missing keys by default, so vertices that never appear as destinations automatically have an in-degree of 0. The extra initialization adds unnecessary complexity and reduces code elegance.

Correct approach: Trust Counter's default behavior:

in_degree_count = Counter(destination for source, destination in edges)
# in_degree_count[vertex] returns 0 if vertex is not in the counter

2. Using a Set or List to Track Destinations Instead of Counter

Some might try to collect all destination vertices in a set and then find the difference:

# Inefficient approach - AVOID
destinations = set()
for source, destination in edges:
    destinations.add(destination)
return [i for i in range(n) if i not in destinations]

Why it's a pitfall: While this works functionally, it's less clear about the underlying logic (counting in-degrees) and doesn't extend well if you later need to know the actual in-degree values for other purposes.

3. Forgetting to Handle Empty Graphs or Graphs with No Edges

If edges is empty (no edges in the graph), some implementations might fail:

# Potential issue if not careful
if not edges:  # Some might think special handling is needed
    return list(range(n))  # This is actually correct but adds unnecessary code

Why it's a pitfall: The original solution already handles this case correctly! When edges is empty, the Counter is empty, so all vertices have in-degree 0 and all are returned. Adding special case handling makes the code more complex without benefit.

4. Incorrect Variable Naming in the Generator Expression

A subtle but important mistake is using confusing variable names when unpacking edges:

# Confusing naming - AVOID
in_degree_count = Counter(from_v for from_v, to_v in edges)  # WRONG!
# This counts source vertices, not destinations!

Why it's a pitfall: This completely reverses the logic, counting out-degrees instead of in-degrees. The result would be vertices that don't have any outgoing edges, which is not what we want.

Correct approach: Use clear, meaningful names:

in_degree_count = Counter(destination for source, destination in edges)
# Or use underscore for unused variables
in_degree_count = Counter(to for _, to in edges)

5. Assuming the Graph is Connected

Some might assume that the minimum set should always have size 1 for a connected graph:

# WRONG assumption
result = [vertex for vertex in range(n) if in_degree_count[vertex] == 0]
if len(result) > 1:
    # Trying to "optimize" by reducing the set - DON'T DO THIS
    return [result[0]]  # WRONG!

Why it's a pitfall: A DAG can have multiple disconnected components or parallel branches that all need separate starting points. The problem asks for the minimum set to reach ALL vertices, not just some of them.

Solution: Trust the algorithm - all vertices with in-degree 0 are necessary and sufficient for the minimum starting set.