Untitled

mail@pastecode.io avatar
unknown
java
2 years ago
1.4 kB
1
Indexable
Never
class Solution {
    public enum Status {
        White,
        Gray,
        Black
    }
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, Status> status = new HashMap<>();
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for(int i = 0; i < numCourses; i++){
            status.put(i, Status.White);
            adj.put(i, new ArrayList());
        }
        for(int[] pre : prerequisites){
            adj.get(pre[1]).add(pre[0]);
        }
        List<Integer> resultList = new ArrayList<>();
        for(int i = 0; i < numCourses; i++){
            if(!dfs(i, adj, status, resultList)){
                return new int[]{};
            }
        }
        int[] result = new int[numCourses];
        int index = 0;
        for(int i = resultList.size() - 1; i >= 0; i--){
            result[index++] = resultList.get(i);
        }
        return result;
    }
    
    public boolean dfs(int course, Map<Integer, List<Integer>> adj, Map<Integer, Status> status, List<Integer> resultList){
        if(status.get(course) == Status.Black) return true;
        if(status.get(course) == Status.Gray) return false;
        
        status.put(course, Status.Gray);
        for(int neighbor : adj.get(course)){
            if(!dfs(neighbor, adj, status, resultList)) return false;
        }
        status.put(course, Status.Black);
        resultList.add(course);
        return true;
    }
}