LeetCode——Course Schedule

165 阅读1分钟

题目描述

题目描述

思路

  • 将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;
    }
}