BiruLyu
5/27/2017 - 6:47 PM

## 207. Course Schedule(# Topological Sort).java

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {

for(int i = 0; i < numCourses; i++){
}

for(int i = 0; i < prerequisites.length; i++){
int start = prerequisites[i][0];
int end = prerequisites[i][1];
}

int[] explored = new int[numCourses];

for(int i = 0; i < numCourses; i++){
if(explored[i] == 2){//优化！！！
continue;
}
return false;
}
}

return true;

}

public boolean hasCycle(List<List<Integer>> adjList, int[] explored, int cur){

explored[cur] = 1;
for(int i = 0; i < adjList.get(cur).size(); i++){

if (explored[temp] == 1) {
return true;
} else if (explored[temp] == 0) {
return true;
}
}
}
explored[cur] = 2;
return false;

}
}

/*
2
[[1,0]]
2
[[1,0],[0,1]]
5
[[0,1],[1,2],[1,3],[1,4],[2,3]]

*/``````
``````class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length < 1 || prerequisites[0].length < 1) return true;
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
}
for (int[] e : prerequisites) {
indegree[e[1]]++;
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
}
}
int cnt = 0;
while (!q.isEmpty()) {
int cur = q.poll();
cnt++;
for (int next : adj.get(cur)) {
if (--indegree[next] == 0) {
q.offer(next);
}
}
}
return cnt == numCourses;
}
}``````