207、课程表
class Solution {
public List<Integer>[] edges;
public int[] ls;
public boolean flag = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new List[numCourses];
for(int i = 0; i < numCourses; i++){
edges[i] = new ArrayList<Integer>();
}
for(int i = 0; i < prerequisites.length; i++){
edges[prerequisites[i][0]].add(prerequisites[i][1]);
}
ls = new int[numCourses];
for(int i = 0; i < numCourses; i++){
if(ls[i]==0){
dfs(i);
if(!flag){
return false;
}
}
}
return true;
}
public void dfs(int index){
ls[index] = 1;
List<Integer> edge = edges[index];
for(Integer integer : edge){
if(ls[integer]==1){
flag = false;
return;
}else if(ls[integer]==0){
dfs(integer);
}
}
ls[index]=2;
}
}
210、课程表 II
class Solution {
public List<Integer>[] edges;
public int[] visited;
public boolean flag = true;
public int[] result;
public int score;
public int[] findOrder(int numCourses, int[][] prerequisites) {
edges = new List[numCourses];
for(int i = 0; i < numCourses; i++){
edges[i] = new ArrayList<>();
}
for(int i = 0; i < prerequisites.length; i++){
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
visited = new int[numCourses];
result = new int[numCourses];
score = numCourses-1;
for(int i = 0; i < numCourses; i++){
if(visited[i]==0){
dfs(i);
if(!flag){
return new int[0];
}
}
}
return result;
}
public void dfs(int index){
visited[index] = 1;
List<Integer> edge = edges[index];
for(Integer integer : edge){
if(visited[integer]==0){
dfs(integer);
if(!flag){
return;
}
}else if(visited[integer]==1){
flag = false;
return;
}
}
visited[index]=2;
result[score--]=index;
}
}