课程表II

LeetCode 210 课程表II

现在你总共有 numCourses 门课需要选，记为0到numCourses - 1。
给你一个数组rerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修bi 。
例如，想要学习课程 0 ，你需要先完成课程1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

/**
 *
 * 执行结果：通过
 * 执行用时：13 ms, 在所有 Java 提交中击败了14.73%的用户
 * 内存消耗：42.5 MB, 在所有 Java 提交中击败了47.69%的用户
 * 通过测试用例：45 / 45
 *
 */
public class CourseScheduleII {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (prerequisites.length == 0) {
            int[] result = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        Graph graph = change(prerequisites);
        Queue<Node> queue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            if (node.in == 0) {
                queue.add(node);
            }
        }
        if (queue.size() == 0) {
            return new int[]{};
        }
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            list.add(poll.val);
            for (Node node : poll.next) {
                node.in -= 1;
                if (node.in == 0) {
                    queue.add(node);
                }
            }
        }
        if (list.size() == graph.nodes.size()) {
            int[] result = new int[numCourses];
            int i = 0;
            while ( i < list.size()) {
                result[i] = list.get(i);
                i++;
            }
            for (int j = 0; i < numCourses; j++){
                if( !list.contains(j)){
                    result[i] = j;
                    i++;
                }
            }
            return result;
        } else {
            return new int[]{};
        }
    }

    public Graph change(int[][] prerequisites) {
        Graph graph = new Graph();
        for (int i = 0; i < prerequisites.length; i++) {
            int to = prerequisites[i][0];
            int from = prerequisites[i][1];
            if (!graph.nodes.containsKey(to)) {
                Node node = new Node(to);
                node.in += 1;
                graph.nodes.put(to, node);
            } else {
                Node node = graph.nodes.get(to);
                node.in += 1;
            }
            if (!graph.nodes.containsKey(from)) {
                Node node = new Node(from);
                node.out += 1;
                node.next.add(graph.nodes.get(to));
                graph.nodes.put(from, node);
            } else {
                Node node = graph.nodes.get(from);
                node.out += 1;
                node.next.add(graph.nodes.get(to));
            }
        }
        return graph;
    }

    public class Node {
        public int val;
        public int in;
        public int out;
        public ArrayList<Node> next;

        public Node() {
        }

        public Node(int val) {
            this.val = val;
            this.in = 0;
            this.out = 0;
            this.next = new ArrayList<Node>();
        }
    }

    public class Graph {
        public HashMap<Integer, Node> nodes;

        public Graph() {
            this.nodes = new HashMap<Integer, Node>();
        }

        public Graph(HashMap<Integer, Node> nodes) {
            this.nodes = nodes;
        }
    }
}