leetcode(210)课程表2

缺乏、安全感 2021-11-01 08:30 235阅读 0赞

课程表2

解题思路：dfs+(邻接矩阵、邻接表)+状态机

要判断是否有环，一定要加上状态机，这里的degree存储的就是状态机：-1(没有被访问)、0(正在被访问)、1(已经被访问)

class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            int len = prerequisites.length;
            boolean[][] queue = new boolean[numCourses][numCourses];
            for(int[] p : prerequisites){
               queue[p[0]][p[1]]=true; 
            }
            int[] degree = new int[numCourses];
            for(int i=0;i<numCourses;i++){
               degree[i] = -1; 
            }
            List<Integer> res = new ArrayList<>();
            for(int i=0;i<numCourses;i++){
                if(dfs(queue,degree,res,numCourses,i)){
                    
                }else{
                    return new int[0];
                }
            }
            int[] result = new int[numCourses];
            int t = 0;
            for(Integer i :res){
                result[t++]=i;
            }
            return result;
        }
        public boolean dfs(boolean[][] queue,int[] degree,List<Integer> res,int numCourses,int p){
            if(degree[p]==1){
                return true;
            }
            if(degree[p]==0){
                return false;
            }
            if(degree[p]==-1){
                degree[p]=0;
                for(int i=0;i<numCourses;i++){
                    if(!queue[p][i]){
                        continue;
                    }
                    if(dfs(queue,degree,res,numCourses,i)){
                    }else{
                        return false;
                    }
                }
                degree[p]=1;
                res.add(p);
                return true;
            }
            return true;
        }
    }

方法2

解题思路：拓扑排序

转载于:https://www.cnblogs.com/erdanyang/p/11156166.html