Grokking the Coding Interview: Patterns for Coding Questions
Vote

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!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from typing import List

class Solution:
    # This is a Topological sort question and does not belong to DFS or BFS 
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        indegree = {}
        result = []
        
       # all nodes will be in 0 indegree initially
        for i in range(n):
            indegree[i] = indegree.get(i, 0)

        # increase the node degree if another node points to it
        for a, b in edges:
            indegree[b] = indegree.get(b, 0)
            indegree[b] += 1

        # find all nodes with 0 degrees
        for edge, degree in indegree.items():
            if degree == 0:
                result.append(edge)
        return result
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
U

Utkarsh Gupta

· 3 years ago

In the below testcase, the expected result is not correct. If you see, the graph has two source nodes with indegree 0, therefore the expected answer should be [1,3] not [1].

WrongAnswer

0.3 ms

Your Input

7

[[1,0],[1,2],[3,4],[4,5],[5,6]]

Output

[1,3]

Expected

[1]

Show 2 replies
Hugh Parry

Hugh Parry

· a year ago

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]: return [node for node in range(n) if node not in set(to_node for _, to_node in edges)]