Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Minimum Number of Vertices to Reach All Nodes(medium)

Problem Statement

Given a directed acyclic graph with n nodes labeled from 0 to n-1, determine the smallest number of initial nodes such that you can access all the nodes by traversing edges. Return these nodes.

Examples

  1. Example 1:

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

  • Expected Output: [0,3]

  • Justification: Starting from nodes 0 and 3, you can reach all other nodes in the graph. Starting from node 0, you can reach nodes 1, 2, and 5. Starting from node 3, you can reach nodes 4 and 2 (and by extension 5).

2

.....

.....

.....

Like the course? Get enrolled and start learning!
P

pjplucinski

· 3 years ago

It seems like one of the provided test cases may be incorrect for the question. Please let me know if I missed something.

Input: n=7, edges=[[0,1],[1,2],[2,3],[4,5],[5,6],[6,4]]

Expected Output (from the course): [0]

(My) Expected Output: [0, 4]

The question specifies that we're provided a directed acyclic graph (DAG). However, this subset of edges ([4,5],[5,6],[6,4]) seems to set up a cycle: 4 -> 5 -> 6 -> 4. The provided solution of counting which nodes have in-degrees of 0 couldn't work for this because none of the nodes of a cycle have an in-degree of 0.

Show 1 reply