额今天这道题目。。。实际上是没做出来的
因为超时了
我算了下算法复杂度大概是O（n^2）
但是花了一个小时搞出来的。。实在是。。不舍得删了。。。留着自己看吧。。。
public class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { HashMap<Integer,LinkedList<Integer>> map=new HashMap<>(); for(int i=0;i<prerequisites.length;i++){ if(map.containsKey(prerequisites[i][0])){ LinkedList<Integer> list=map.get(prerequisites[i][0]); list.add(prerequisites[i][1]); map.put(prerequisites[i][0],list); }else{ LinkedList<Integer> list=new LinkedList<>(); list.add(prerequisites[i][1]); map.put(prerequisites[i][0],list); } } Set<Integer> set=new HashSet<>(); LinkedList<Integer> answear=new LinkedList<>(); LinkedList<Integer> table=new LinkedList<>(); for(int i=0;i<numCourses;i++){ if(!map.containsKey(i)){ answear.add(i); set.add(i); }else{ table.add(i); } } boolean mark2=false; int len=table.size(); while(table.size()!=0){ for(int i=0;i<table.size();i++){ LinkedList<Integer> temp=map.get(table.get(i)); boolean mark=true; for(int j=0;j<temp.size();j++){ if(!set.contains(temp.get(j))){ mark=false; break; } } if(mark){ answear.add(table.get(i)); set.add(table.get(i)); table.remove(i); i--; } } if(len>table.size()){ len=table.size(); }else{ mark2=true; break; } } if(mark2){ int[] nums2=new int[0]; return nums2; } int[] nums=new int[answear.size()]; for(int i=0;i<answear.size();i++){ nums[i]=answear.get(i); } return nums; } }额下面是标准答案之一，供学习 public class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(numCourses); for (int i = 0; i < numCourses; i++) adj.add(i, new ArrayList<>()); for (int i = 0; i < prerequisites.length; i++) adj.get(prerequisites[i][1]).add(prerequisites[i][0]); boolean[] visited = new boolean[numCourses]; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < numCourses; i++) { if (!topologicalSort(adj, i, stack, visited, new boolean[numCourses])) return new int[0]; } int i = 0; int[] result = new int[numCourses]; while (!stack.isEmpty()) { result[i++] = stack.pop(); } return result; } private boolean topologicalSort(List<List<Integer>> adj, int v, Stack<Integer> stack, boolean[] visited, boolean[] isLoop) { if (visited[v]) return true; if (isLoop[v]) return false; isLoop[v] = true; for (Integer u : adj.get(v)) { if (!topologicalSort(adj, u, stack, visited, isLoop)) return false; } visited[v] = true; stack.push(v); return true; } }