LeetCode：210课程表Ⅱ（图论：拓扑排序判断是否有环）

做本题之前最好先做了LeetCode：207课程表，见本人另一篇博客http://t.csdnimg.cn/vSXgN

题目

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses – 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses – 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

思路

这道题和LC207不同的是，它需要返回拓扑排序的路径。除此之外，不在拓扑排序路径，或者说不在图中的节点也需要返回，但是无所谓插入的顺序。所以本人在最后判断了一下哪些节点没有在图中出现，然后插入在了拓扑排序节点数组的最后面。
注意返回空数组是return new int[0]不是return null;

代码

class Solution {public class Graph{public HashMap<Integer,Node> nodes;public HashSet<Edge> edges;public Graph(){nodes = new HashMap<>();edges = new HashSet<>();}}public class Node{public int value;public int in;public ArrayList<Node> nexts;public Node(int value){this.value = value;in=0;nexts = new ArrayList<>();}}public class Edge{public Node from;public Node to;public Edge(Node from, Node to){this.from = from;this.to = to;}}public Graph createGraph(int[][] prerequisites){Graph graph = new Graph();for(int i=0;i<prerequisites.length;i++){int fromVal = prerequisites[i][1];int toVal = prerequisites[i][0]; if(!graph.nodes.containsKey(fromVal)) graph.nodes.put(fromVal, new Node(fromVal));if(!graph.nodes.containsKey(toVal)) graph.nodes.put(toVal, new Node(toVal));Node fromNode = graph.nodes.get(fromVal);Node toNode = graph.nodes.get(toVal);Edge edge = new Edge(fromNode, toNode);toNode.in++;graph.edges.add(edge);fromNode.nexts.add(toNode);}returngraph;}public int[] findOrder(int numCourses, int[][] prerequisites) {int[] result = new int[numCourses];//存放结果Graph graph = createGraph(prerequisites);HashMap<Node,Integer> inMap = new HashMap<>();//一个节点对应的剩余的入度Queue<Node> zeroInQueue = new LinkedList<>();//存放着入度为0的节点for(Node node:graph.nodes.values()){inMap.put(node, node.in);if(node.in==0) zeroInQueue.add(node);}int realnum=0;//拓扑排序路径的节点，即不成环的节点数量while(!zeroInQueue.isEmpty()){Node cur = zeroInQueue.poll();result[realnum]=cur.value;realnum++;for(Node next:cur.nexts){int newin = inMap.get(next)-1;inMap.put(next,newin);if(newin==0) zeroInQueue.add(next);}}int num = graph.nodes.size();if(realnum!=num) return new int[0];//如果不成环的节点数和图中的节点数不相等，说明有环存在，返回一个空数组。int res=0;//res表示其他没在图中出现的节点的数量if(numCourses!=num){//如果课程数和图的节点数不相等，直接判断是哪些节点没有在图中出现，插入到result最后面。for(int i=0;i<numCourses;i++){if(!graph.nodes.containsKey(i)) {result[realnum+res]=i;res++;}}}return result;}}

13ms，击败14.65%使用 Java 的用户