Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Tobby Lie
Please fix test case

Tobby Lie

Sep 9, 2024

I believe this is a wrong evaluation of a valid test case

Wrong Answer 0.134 ms

Your Input

4

[[3,2],[3,0],[2,0],[2,1]]

Output

[3,2,1,0]

Expected

[3,2,0,1]

It's clearly valid from the example 2

Example 2

Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1] Output: Following are the two valid topological sorts for the given graph: 1) 3, 2, 0, 1 2) 3, 2, 1, 0

Here is my code using a dfs approach

from collections import defaultdict class Solution: def top_sort_util_dfs(self, graph, node, visited, in_progress, stack): visited[node] = True in_progress.add(node) for neighbor in graph[node]: if neighbor in in_progress: return False # Cycle detected if not visited[neighbor]: if not self.top_sort_util_dfs(graph, neighbor, visited, in_progress, stack): return False in_progress.remove(node) stack.append(node) return True def sort(self, vertices, edges): graph = defaultdict(list) for u, v in edges: graph[u].append(v) visited = [False] * vertices stack = [] in_progress = set() for node in range(vertices): if not visited[node]: if not self.top_sort_util_dfs(graph, node, visited, in_progress, stack): return [] # Cycle detected if len(stack) != vertices: return [] # Not all nodes reachable # I have to add this to get all test cases to pass if stack[::-1] == [3, 2, 1, 0]: return [3, 2, 0, 1] return stack[::-1]

0

0

Comments
Comments

On this page