LeetCode 210 Course Schedule II

// 太慢了!
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        final int[] res = new int[numCourses];
        if (numCourses == 0) {
            return res;
        }
        if (prerequisites.length == 0) {
            for (int i = 0; i < numCourses; i++) {
                res[i] = i;
            }
            return res;
        }
        
        final Stack<Integer> stack = new Stack<>();
        final Map<Integer, Set<Integer>> graph = new HashMap<>();
        final Map<Integer, Integer> indegree = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new HashSet<>());
            indegree.put(i, 0);
        }
        
        for (final int[] edge : prerequisites) {
            graph.get(edge[0]).add(edge[1]);
            indegree.merge(edge[1], 1, Integer::sum);
        }
        
        final Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree.get(i) == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            final int front = queue.poll();
            stack.push(front);
            for (final int adj : graph.get(front)) {
                indegree.merge(adj, -1, Integer::sum);
                if (indegree.get(adj) == 0) {
                    queue.offer(adj);
                }
            }
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (indegree.get(i) != 0 ){
                return new int[0];
            }
        }
        
        for (int i = 0; i < numCourses; i++) {
            res[i] = stack.pop();
        }
        return res;
    }
}
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        final int[] res = new int[numCourses];
        if (numCourses == 0) return res;
        if (prerequisites.length == 0) {
            for (int i = 0; i < numCourses; i++) res[i] = i;
            return res;
        }
        
        final Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; i++) graph.put(i, new HashSet<>());
        for (final int[] edge: prerequisites) graph.get(edge[0]).add(edge[1]);
        
        final Queue<Integer> queue = new LinkedList<>();
        final int[] visited = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (dfsTopoSort(i, graph, visited, queue)) {
                    return new int[0];
                }
            }
        }
        
        for (int i = 0; i < numCourses; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
    
    private boolean dfsTopoSort(final int v, final Map<Integer, Set<Integer>> graph, final int[] visited, final Queue<Integer> queue) {
        if (visited[v] == -1) return true;
        if (visited[v] == 1) return false;
        visited[v] = -1;
        for (final int adj : graph.get(v)) {
            if (dfsTopoSort(adj, graph, visited, queue)) {
                return true;
            }
        }
        visited[v] = 1;
        queue.offer(v);
        return false;
    }
}