Back to course home
0% completed
Vote For New Content
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