1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
|
public int[] findOrder(int numCourses, int[][] prerequisites) { if (numCourses <= 1) return new int[1]; HashMap<Integer, HashSet<Integer>> graph = new HashMap<>(); int[] inlink = new int[numCourses]; for (int i = 0; i < prerequisites.length; ++i) { int u = prerequisites[i][1], v = prerequisites[i][0]; if (graph.containsKey(u)) { if (graph.get(u).contains(v)) continue; inlink[v] += 1; graph.get(u).add(v); } else { inlink[v] += 1; HashSet<Integer> set = new HashSet<>(); set.add(v); graph.put(u, set); } } return bfs(graph, inlink); } public int[] bfs(HashMap<Integer, HashSet<Integer>> graph, int[] inlink) { int[] ans = new int[inlink.length]; Queue<Integer> q = new LinkedList<>(); for (int i = 0; i < inlink.length; ++i) { if (inlink[i] == 0) q.offer(i); } int index = 0; while (!q.isEmpty()) { int u = q.poll(); ans[index++] = u; if (graph.containsKey(u) == false) continue; for (int i : graph.get(u)) { inlink[i] -= 1; if (inlink[i] == 0) q.offer(i); } } for (int i : inlink) { if (i != 0) return new int[0]; } return ans; }
|
近期评论