Leetcode # 207 (Python): Course Schedule

정욱·2021년 4월 18일
0

Leetcode

목록 보기
10/38
post-custom-banner

Course Schedule

  • Difficulty: Medium
  • Type: DFS/BFS
  • link

Problem

Solution

  • Use DFS to search for cylcic structure in graph
  • Implement tree pruning by skipping the visited node
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for course, prereq in prerequisites:
            graph[course].append(prereq)

        traced = set()
        visited = set()

        def dfs(i):
            # If graph is cyclic, return false
            if i in traced:
                return False
            # If already visited, return true
            if i in visited:
                return True
            traced.add(i)
            for y in graph[i]:
                if not dfs(y):
                    return False
            # Remove node when finsihed with search
            traced.remove(i)
            # Add node to visited when search finished
            visited.add(i)
            return True

        # Run DFS to find cyclic graph structure
        for x in list(graph):
            if not dfs(x):
                return False
        return True
post-custom-banner

0개의 댓글