Leetcode 207

finding a cycle

언어: python3

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # find if cycle exists
        graph = collections.defaultdict(list)
        for latter,pre in prerequisites:
            graph[latter].append(pre)
        
        visited = set()
        trace = set()
        
        def dfs(i):
            if i in trace:
                return False
            if i in visited:
                return True
            
            trace.add(i)
            for pre in graph[i]:
                if not dfs(pre):
                    return False
            
            trace.remove(i)
            visited.add(i)
            
            return True
        
        for key in graph.keys():
            if not dfs(key):
                return False
        
        '''
        for x in list(graph):
            if not dfs(x):
                return False
        '''
        return True
            

• graph.keys() 로 iteration할 경우 default dictionary가 null error를 없애기 위해 임의로 요소를 추가하기 때문에 iteration 도중 size 바뀌는 에러가 발생
• 이를 보완하기 위해 list(dictionary)와 같이 값을 복사하여 사용하는 것이 필요함
• dfs 함수는 사이클이 있는지 참, 거짓 여부를 반환하며 iteration이 directed graph의 반대방향으로 돌기 때문에 이를 감안해야 한다