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?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
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.
Topological Sort: http://www.jianshu.com/p/5880cf3be264
Solution1：Topological sort from Indegree==0 (by BFS)
思路：从indegree==0的地方bfs向内部找，找到将该node剪掉(其置为visited或将其indegree无效 并 更新其neighbors的indegree--)，然后继续从indegree==0的地方找。当找不到的时候退出，看是否遍历了全部N个结点。
(queue也可以该成stack, 但整体思路是BFS的，内部小部分dfs/bfs都可以)
(不用queue起始也可以的，hashmap记录indegree==0的标号，或是每次再搜索别的indegree==0的结点，整体思路是BFS的)
BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise we have found one. We set its reduce the indegrees of all its neighbors by 1. This process should be repeated for n (number of nodes) times. If not, we return false, otherwise we will return true.
实现1a: 邻接矩阵
Time Complexity: O(V ^ 2) Space Complexity: O(V ^ 2)
实现1b: 邻接表 (recommended)
Time Complexity: O(V + E) Space Complexity: O(V + E)
Solution2：Topological sort (DFS) 看是否onpath上有cycle
思路：任意起始dfs向深找，过程记录global visited，global visited的说明已经dfs过了不用处理，并keep一个on_path的visited，就是一次dfs到底过程中的on_path visited，如果碰到on_path visited 说明有loop不能够完成Topological Sort。on_path visited的更新类似回溯，到底后回溯回来一步要将该结点的on_path visited再改为false.
If it meets a node which was visited in the current process of DFS visit, a cycle is detected and we will return false. Otherwise it will start from another unvisited node and repeat this process till all the nodes have been visited. Note that you should make two records: one is to record all the visited nodes and the other is to record the visited nodes in the current DFS visit.
这里实现用了 邻接表
Time Complexity: O(V + E) Space Complexity: O(V + E) 递归缓存
Solution1a Code：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[][] matrix = new int[numCourses][numCourses]; // i -> j
int[] indegree = new int[numCourses];
// graph build
for (int i = 0; i < prerequisites.length; i++) {
int pre = prerequisites[i][1];
int post = prerequisites[i][0];
indegree[post]++;
matrix[pre][post] = 1;
}
// bfs from nodes whose degree == 0
int count = 0;
Queue<Integer> queue = new LinkedList();
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int i = 0; i < numCourses; i++) {
if (matrix[course][i] != 0) {
if (--indegree[i] == 0)
queue.offer(i);
}
}
}
return count == numCourses;
}
}
Solution1b Code：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
// O(V + E)
// graph build
// graph = adj_list init
List<List<Integer>> graph = new ArrayList<List<Integer>>();
for(int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<Integer>()); // LinkedList is also OK
}
// O(E) part
for (int i = 0; i < prerequisites.length; i++) {
int pre = prerequisites[i][1];
int post = prerequisites[i][0];
indegree[post]++;
graph.get(pre).add(post);
}
// O(V) part
// bfs from nodes whose degree == 0
int count = 0;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
List<Integer> next_list = graph.get(course);
for(int i = 0; i < next_list.size(); i++) {
if (--indegree[next_list.get(i)] == 0) {
queue.offer(next_list.get(i));
}
}
}
return count == numCourses;
}
}
Solution2 Code：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// O(V + E)
// graph = adj_list init
List<List<Integer>> graph = new ArrayList<List<Integer>>();
for(int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<Integer>()); // LinkedList is also OK
}
boolean[] visited = new boolean[numCourses];
boolean[] onpath = new boolean[numCourses];
// O(E) part
// graph(adj_list) build
for (int i = 0; i < prerequisites.length; i++) {
int pre = prerequisites[i][1];
int post = prerequisites[i][0];
graph.get(pre).add(post);
}
// O(V) part
for(int i = 0; i < numCourses; i++) {
if(!visited[i] && dfs_cycle(graph, i, visited, onpath)) {
return false;
}
}
return true;
}
// dfs to detect cycle by using onpath, if detected: return true;
private boolean dfs_cycle(List<List<Integer>> graph, int node, boolean[] visited, boolean[] onpath) {
onpath[node] = true;
visited[node] = true;
for(int i = 0; i < graph.get(node).size(); i++) {
int neighbor = graph.get(node).get(i);
if (onpath[neighbor] || (!visited[neighbor] && dfs_cycle(graph, neighbor, visited, onpath))) {
return true;
}
}
// onpath step back
onpath[node] = false;
return false;
}
}
Solution2.round1 Code：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(numCourses == 0 || prerequisites == null || prerequisites.length == 0) return true;
// graph define
List<List<Integer>> graph = new ArrayList<>();
for(int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// graph build
for(int i = 0; i < prerequisites.length; i++) {
graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
boolean[] g_visited = new boolean[numCourses];
boolean[] on_path = new boolean[numCourses];
for(int i = 0; i < numCourses; i++) {
if(!g_visited[i] && dfsDetectCycle(graph, i, g_visited, on_path)) {
return false;
}
}
return true;
}
private boolean dfsDetectCycle(List<List<Integer>> graph, int cur, boolean[] g_visited, boolean[] on_path) {
g_visited[cur] = true;
on_path[cur] = true;
List<Integer> neighbors = graph.get(cur);
for(Integer neighbor: neighbors) {
if(on_path[neighbor]) {
return true;
}
if(g_visited[neighbor]) continue;
if(dfsDetectCycle(graph, neighbor, g_visited, on_path)) {
return true;
}
}
on_path[cur] = false;
return false;
}
}
Tag_Round1 Code
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(numCourses == 0 || prerequisites == null || prerequisites.length == 0) return true;
// build graph
List<List<Integer>> graph = new ArrayList<>();
for(int i = 0; i< numCourses; i++) {
graph.add(new ArrayList<>());
}
// init graph
for(int i = 0; i < prerequisites.length; i++) {
int pre = prerequisites[i][1];
int post = prerequisites[i][0];
graph.get(pre).add(post);
}
boolean[] g_visited = new boolean[numCourses];
boolean[] on_path = new boolean[numCourses];
// dfs detect cycle
for(int i = 0; i < graph.size(); i++) {
if(g_visited[i] || graph.get(i).size() == 0) continue;
if(dfsCycle(graph, i, g_visited, on_path)) {
return false;
}
}
return true;
}
private boolean dfsCycle(List<List<Integer>> graph, int start_id, boolean[] g_visited, boolean[] on_path) {
g_visited[start_id] = true;
on_path[start_id] = true;
List<Integer> next_list = graph.get(start_id);
for(int i = 0; i < next_list.size(); i++) {
int next = next_list.get(i);
if(on_path[next]) return true;
if(g_visited[next]) continue;
if(dfsCycle(graph, next, g_visited, on_path)) return true;
}
on_path[start_id] = false;
return false;
}
}
