题目描述
思路
- 将prerequisites读取写成从某个节点出发可以达到的下一个点是哪些。
比如:[1,0][0,1][2,1]就转变为
0:[1]
1:[0,2]
2:[]
-
设置visited数组,来判断某节点处于未访问状态(0)、正在访问状态(-1)以及已访问状态(1)这三种状态。
-
使用DFS来访问每个节点判断是否存在环
代码实现
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList<ArrayList<Integer>> processResult = new ArrayList<ArrayList<Integer>>();
int[] visited = new int[numCourses];
for(int i = 0; i < numCourses; i++){
ArrayList<Integer> temp = new ArrayList<Integer>();
processResult.add(temp);
visited[i] = 0;
}
for(int i = 0; i < prerequisites.length; i++){
processResult.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
for(int i=0;i<numCourses;i++){
for(Integer num:processResult.get(i)){
System.out.println(num);
}
}
for(int i = 0;i<numCourses;i++){
if(!dfs(i, processResult,visited)){
return false;
}
}
return true;
}
public boolean dfs(int i,ArrayList<ArrayList<Integer>> processResult, int[] visited){
if(visited[i] == 1){
return true;
}else if(visited[i] == -1){
return false;
}else{
ArrayList<Integer> path = processResult.get(i);
visited[i] = -1;
for(Integer node:path){
if(!dfs(node, processResult, visited)){
return false;
}
}
visited[i] = 1;
}
return true;
}
}