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.reibang.com/p/5880cf3be264
Solution1：Topological sort from Indegree==0 (by BFS)
思路：從indegree==0的地方bfs向內(nèi)部找奈泪，找到將該node剪掉(其置為visited或?qū)⑵鋓ndegree無效 并 更新其neighbors的indegree--)，然后繼續(xù)從indegree==0的地方找鞭铆。當找不到的時候退出娜膘，看是否遍歷了全部N個結(jié)點嘀粱。
(queue也可以該成stack, 但整體思路是BFS的，內(nèi)部小部分dfs/bfs都可以)
(不用queue起始也可以的，hashmap記錄indegree==0的標號岛都，或是每次再搜索別的indegree==0的結(jié)點风瘦，整體思路是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.
實現(xiàn)1a: 鄰接矩陣
Time Complexity: O(V ^ 2) Space Complexity: O(V ^ 2)
實現(xiàn)1b: 鄰接表 (recommended)
Time Complexity: O(V + E) Space Complexity: O(V + E)
Solution2：Topological sort (DFS) 看是否onpath上有cycle
思路：任意起始dfs向深找队魏，過程記錄global visited，global visited的說明已經(jīng)dfs過了不用處理万搔，并keep一個on_path的visited胡桨，就是一次dfs到底過程中的on_path visited，如果碰到on_path visited 說明有l(wèi)oop不能夠完成Topological Sort瞬雹。on_path visited的更新類似回溯昧谊，到底后回溯回來一步要將該結(jié)點的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.
這里實現(xiàn)用了 鄰接表
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;
}
}
