拓扑排序问题

LeetCode 207 课程表

你这个学期必须选修 numCourses 门课程，记为0到numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组prerequisites 给出，
其中prerequisites[i] = [ai, bi] ，表示如果要学习课程ai 则 必须 先学习课程 bi 。
例如，先修课程对[0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

/**
 *
 * 执行结果：通过
 * 执行用时：9 ms, 在所有 Java 提交中击败了16.72%的用户
 * 内存消耗：41.4 MB, 在所有 Java 提交中击败了81.16%的用户
 * 通过测试用例：51 / 51
 *
 */
public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites.length == 0) {
            return true;
        }
        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 false;
        }
        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()) {
            return true;
        } else {
            return false;
        }
    }

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