Course Schedule

https://leetcode.com/problems/course-schedule/description/

BFS

Use topological sorting.

The graph of courses should be Directed Acyclic Graph

http://www.geeksforgeeks.org/topological-sorting/

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.

Note: degree[node] means how many vertex goes into the node.
If the degree of a node is 0, then put the node in the queue

from collections import defaultdict
from collections import deque
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """

        graph = defaultdict(set)
        degree = {} #how many vertex goes to it
        queue = deque()
        cnt = 0

        for i in range(numCourses):
            degree[i] = 0

        for c, v in prerequisites:
            graph[v].add(c)
            degree[c] += 1

        for i in range(len(degree)):
            if degree[i] == 0:
                queue.append(i)


        while len(queue) != 0:
            v = queue.popleft()
            cnt += 1
            for i in graph[v]:
                degree[i] -= 1
                if degree[i] == 0:
                    queue.append(i)

        return cnt == numCourses

DFS

if node v is not visited, then mark it as 0.
if node v is being visited, then mark it as -1. If we find a vertex marked as -1 in DFS, we know that there is a ring.
if node v has been visited, then mark it as 1. If a vertex was marked 1, then no rings contain v or its successors.

from collections import defaultdict, deque, Counter
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """

        def dfs(v, graph, visited):
            if visited[v] == 1:
                return True

            if visited[v] == -1:
                return False

            visited[v] = -1
            for neighbor in graph[c]:
                if not dfs(neighbor, graph, visited):
                    return False

            visited[v] = 1
            return True


        graph = defaultdict(set)
        visited = numCourses * [0]

        for c, v in prerequisites:
            graph[v].add(c)

        for i in range(numCourses):
            if not dfs(i, graph, visited):
                return False
        return True