LeetCode 207. Course Schedule--有向图找环--面试算法题--DFS递归,拓扑排序迭代--Python

2020/01/29 LeetCode 数据结构 共 3338 字,约 10 分钟

题目地址:Course Schedule - LeetCode

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.


The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.






class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        s = {}
        res = set()
        flag = 0

        def helper(begin=-1, find=set()):
            nonlocal flag, res, s
            for i in s[begin]:
                if i not in res:
                    if i in find:
                        flag = 1
                    helper(i, find=find)

        for i in range(0, numCourses):
            s[i] = set()
        for i in prerequisites:
        for i in range(0, numCourses):
            helper(begin=i, find={i})
            if flag == 1:
                return False
        return True


class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        graph = [[] for _ in range(numCourses)]
        visited = [0 for _ in range(numCourses)]
        # create graph
        for pair in prerequisites:
            x, y = pair
        # visit each node
        for i in range(numCourses):
            if not self.dfs(graph, visited, i):
                return False
        return True
    def dfs(self, graph, visited, i):
        # if ith node is marked as being visited, then a cycle is found
        if visited[i] == -1:
            return False
        # if it is done visted, then do not visit again
        if visited[i] == 1:
            return True
        # mark as being visited
        visited[i] = -1
        # visit all the neighbours
        for j in graph[i]:
            if not self.dfs(graph, visited, j):
                return False
        # after visit all the neighbours, mark it as done visited
        visited[i] = 1
        return True


class Solution:
    class Course(object):
        def __init__(self):
            self.being_visit, self.visit_done = False, False
            self.pre_course = []

        def is_cyclic(self):
            if self.visit_done is True:
                return False
            if self.being_visit is True:
                return True
            self.being_visit = True
            for course in self.pre_course:
                if course.is_cyclic():
                    return True
            self.being_visit = False
            self.visit_done = True
            return False

    def canFinish(self, num_courses, prerequisites) -> bool:
        l = [self.Course() for _ in range(0, num_courses)]
        for (course1, course2) in prerequisites:
        for i in range(0, num_courses):
            if l[i].is_cyclic():
                return False
        return True

标准的更正式更快的解法是拓扑排序(Topological Sorting),可以参考:Kahn’s algorithm for Topological Sorting - GeeksforGeeks

class Solution:
    def canFinish(self, num_courses, prerequisites) -> bool:
        vertices = num_courses
        adj_list = [[] for _ in range(0, vertices)]
        in_degree = [0 for _ in range(0, vertices)]
        for (course1, course2) in prerequisites:
            in_degree[course2] += 1
        q = [i for i in range(0, vertices) if in_degree[i] == 0]
        count = 0
        while q:
            front = q.pop(0)
            for i in adj_list[front]:
                in_degree[i] -= 1
                if in_degree[i] < 0:
                    return False
                elif in_degree[i] == 0:
            count += 1
        if count == vertices:
            return True
            return False


Table of Contents