[leetcode] Course Schedule II

貌似这是Topological sorting...上网看了下Topological的解释 思路就清晰了....

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

public class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { int[] inDegree = new int[numCourses]; List<HashSet<Integer>> out = new ArrayList<HashSet<Integer>>(); for (int i = 0; i < numCourses; i++){ out.add(new HashSet<Integer>()); } for (int i = 0; i < prerequisites.length; i++){ if (!out.get(prerequisites[i][1]).contains(prerequisites[i][0])){ inDegree[prerequisites[i][0]]++; out.get(prerequisites[i][1]).add(prerequisites[i][0]); } } Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < inDegree.length; i++){ if (inDegree[i] == 0) queue.add(i); } int result[] = new int[numCourses]; int curPtr = 0; while (!queue.isEmpty()){ int current = queue.poll(); result[curPtr++] = current; HashSet<Integer> outCourses = out.get(current); for (Integer temp:outCourses){ inDegree[temp]--; out.get(temp).remove(current); if (inDegree[temp] == 0) queue.add(temp); } } if (curPtr != numCourses) return new int[0]; return result; } }