Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

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

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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

Reading Progress

0%

Vote for new content