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.


Note:


       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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Directed graphs

Starter code: class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        

Solutions:
class Solution(object):

	def canFinish(self, numCourses, prerequisites):
		graph = [[] for _ in range(numCourses)]
		visited = [0 for _ in range(numCourses)]
		for pair in prerequisites:
			(x, y) = pair
			graph[x].append(y)
		for i in range(numCourses):
			if not self.dfs(graph, visited, i):
				return False
		return True

	def dfs(self, graph, visited, i):
		if visited[i] == -1:
			return False
		if visited[i] == 1:
			return True
		visited[i] = -1
		for j in graph[i]:
			if not self.dfs(graph, visited, j):
				return False
		visited[i] = 1
		return True


class Solution:

	def canFinish(self, numCourses, prerequisites):
		V = numCourses
		edges = []
		for _ in range(V):
			edges.append(set())
		for p in prerequisites:
			(v2, v1) = p
			edges[v1].add(v2)
		checked = set()

		def detect_cycle(x, visited):
			visited.add(x)
			checked.add(x)
			for v in edges[x]:
				if v in visited:
					return True
				if detect_cycle(v, visited):
					return True
			visited.remove(x)
			return False
		for v in range(V):
			if v in checked:
				continue
			if detect_cycle(v, set()):
				return False
		return True


class Solution:

	def canFinish(self, numCourses, prerequisites):
		N = numCourses
		indegree = [0] * N
		O = [set() for _ in range(N)]
		for (b, a) in prerequisites:
			O[a].add(b)
			indegree[b] += 1
		stack = [c for c in range(N) if indegree[c] == 0]
		done = 0
		while stack:
			i = stack.pop()
			done += 1
			for j in O[i]:
				indegree[j] -= 1
				if indegree[j] == 0:
					stack.append(j)
		return done == N


class Solution:

	def canFinish(self, numCourses, prerequisites):
		pre_count = [0] * numCourses
		next_courses = [[] for _ in range(numCourses)]
		for (cur, pre) in prerequisites:
			next_courses[pre].append(cur)
			pre_count[cur] += 1
		q = []
		for (i, count) in enumerate(pre_count):
			if count == 0:
				q.append(i)
		finish_num = 0
		while q:
			course = q.pop(0)
			finish_num += 1
			for next_course in next_courses[course]:
				pre_count[next_course] -= 1
				if pre_count[next_course] == 0:
					q.append(next_course)
		return finish_num == numCourses


class Solution:

	def canFinish(self, numCourses, prerequisites):
		graph = [[] for _ in range(numCourses)]
		visit = [0 for _ in range(numCourses)]
		for (x, y) in prerequisites:
			graph[x].append(y)

		def dfs(c, v):
			if v[c] == 2:
				return False
			if v[c] == 1:
				return True
			v[c] = 1
			for i in graph[c]:
				if dfs(i, v):
					return True
			v[c] = 2
			return False
		for j in range(numCourses):
			if dfs(j, visit):
				return False
		return True


class Solution:

	def canFinish(self, numCourses, prerequisites):
		in_degrees = collections.defaultdict(int)
		edges = collections.defaultdict(list)
		for i in range(0, numCourses):
			in_degrees[i] = 0
		for prerequisty in prerequisites:
			start = prerequisty[1]
			end = prerequisty[0]
			edges[start].append(end)
			in_degrees[end] += 1
		queue = collections.deque()
		for i in range(0, numCourses):
			if in_degrees[i] == 0:
				queue.append(i)
		count = 0
		while len(queue) > 0:
			node = queue.popleft()
			count += 1
			for neighbor in edges[node]:
				in_degrees[neighbor] -= 1
				if in_degrees[neighbor] == 0:
					queue.append(neighbor)
		return count == numCourses


class Solution:

	def canFinish(self, numCourses, prerequisites):
		course_map = {i: [] for i in range(numCourses)}
		degree = [0 for i in range(numCourses)]
		q = []
		counter = 0
		for (c, p) in prerequisites:
			course_map[c].append(p)
			degree[p] += 1
		for i in range(numCourses):
			if degree[i] == 0:
				q.append(i)
				counter += 1
		while q:
			cur = q.pop(0)
			for p in course_map[cur]:
				degree[p] -= 1
				if degree[p] == 0:
					q.append(p)
					counter += 1
		return counter == numCourses


class Solution:

	def canFinish(self, n, prerequisites):

		def ok(node):
			if seens[node] == -1:
				return False
			if not seens[node]:
				seens[node] = -1
				for pre in pres[node]:
					if not ok(pre):
						return False
				seens[node] = 1
			return True
		pres = [[] for _ in range(n)]
		for (cur, pre) in prerequisites:
			pres[cur].append(pre)
		seens = [0] * n
		for node in range(n):
			if not ok(node):
				return False
		return True


class Solution:

	def canFinish(self, numCourses, prerequisites):
		from collections import deque

		class Vertex(object):

			def __init__(self):
				self.inDegree = 0
				self.visited = False
				self.adjList = []
				self.invAdjList = []

			def info(self):
				print(self.adjList)
				print(self.invAdjList, self.inDegree)
				print(self.visited)
		vertices = []
		for _ in range(numCourses):
			vertices.append(Vertex())
		for i in prerequisites:
			pre = i[0]
			post = i[1]
			vertices[pre].adjList.append(post)
			vertices[post].inDegree += 1
			vertices[post].invAdjList.append(pre)
		q = deque()
		coursesLearned = []
		for i in range(numCourses):
			if vertices[i].inDegree == 0:
				q.append(i)
		while q:
			course = q.popleft()
			coursesLearned.append(course)
			vertices[course].visited = True
			for c2 in vertices[course].adjList:
				vertices[c2].inDegree -= 1
				if vertices[c2].inDegree == 0:
					q.append(c2)
		return len(coursesLearned) == numCourses


class Solution:

	def canFinish(self, numCourses, prerequisites):
		N = numCourses
		O = [set() for _ in range(N)]
		for (b, a) in prerequisites:
			O[a].add(b)
		color = [0] * N

		def dfs(i):
			if color[i] == -1:
				return False
			elif color[i] == 1:
				return True
			color[i] = -1
			if any((not dfs(j) for j in O[i])):
				return False
			color[i] = 1
			return True
		return all(map(dfs, range(N)))


class Solution:

	def canFinish(self, numCourses, prerequisites):
		edges = {i: [] for i in range(numCourses)}
		degree = [0 for i in range(numCourses)]
		for (k, v) in prerequisites:
			edges[v].append(k)
			degree[k] += 1
		q = []
		for i in range(numCourses):
			if degree[i] == 0:
				q.append(i)
		count = 0
		while q:
			node = q.pop()
			count += 1
			for nn in edges[node]:
				degree[nn] -= 1
				if degree[nn] == 0:
					q.append(nn)
		return count == numCourses