JB graph problem

mail@pastecode.io avatar
unknown
python
2 years ago
926 B
1
Indexable
Never
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        visited = set()
        self.visited_list = []

        graph = self.build_graph(prerequisites)
        
        for i in range(numCourses):
            if not self.explore(i, graph, visited):
                if not len(self.visited_list):
                    return []
    
        return self.visited_list

    def explore(self, src, graph, visited):

        if src in visited:
            return False
        
        visited.add(src)
        
        for neighbour in graph[src]:
            if not self.explore(neighbour, graph, visited):
                return False
        
        self.visited_list.append(src)
        return True
        
    
    def build_graph(self, edges):
        graph = collections.defaultdict(list)

        for a, b in edges:
            graph[a].append(b)
        return graph