力扣210. 课程表 II 【medium 拓扑排序 java】 同lintcode616

题目描述

拓扑排序

图、拓扑排序 核心数据结构：

      static class Node {
            public int data;
            public int in;
            public List<Node> nexts;

            public Node(int data) {
                this.data = data;
                this.in = 0;
                this.nexts = new ArrayList<>();
            }
        }

Java答案

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        
  //拓扑排序
            Map<Integer, Node> tp = new HashMap<>();
            for (int i = 0; i < numCourses; i++) {
                tp.put(i, new Node(i));
            }

            for (int[] item : prerequisites) {
                int f = item[1], t = item[0];
                if (!tp.containsKey(f))
                    tp.put(f, new Node(f));

                if (!tp.containsKey(t))
                    tp.put(t, new Node(t));

                Node nodef = tp.get(f);
                Node nodet = tp.get(t);
                nodef.nexts.add(nodet);
                nodet.in++;
            }

            Queue<Node> q0 = new LinkedList<>();
            for (int k : tp.keySet()) {
                if (tp.get(k).in == 0) {
                    q0.add(tp.get(k));
                }
            }

            int cnt = 0;
            int[] ans = new int[numCourses];
            int idx = 0;
            while (!q0.isEmpty()) {
                int size = q0.size();
                cnt += size;
                for (int i = 0; i < size; i++) {
                    Node node = q0.poll();
                    ans[idx++] = node.data;
                    for (Node next : node.nexts) {
                        if (--next.in == 0) {
                            q0.add(next);
                        }
                    }
                }
            }

            if (cnt != numCourses) return new int[0];
            return ans;
        }

        static class Node {
            public int data;
            public int in;
            public List<Node> nexts;

            public Node(int data) {
                this.data = data;
                this.in = 0;
                this.nexts = new ArrayList<>();
            }
        }
}