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
| class Program { public static List<Integer> topologicalSort(List<Integer> jobs, List<Integer[]> deps) { Map<Integer, Integer> dependencyNum = new HashMap<>(); Map<Integer, List<Integer>> dependents = new HashMap<>(); Queue<Integer> q = new LinkedList<>(); List<Integer> result = new ArrayList<>(); for (Integer[] dep : deps) { if (!dependents.containsKey(dep[0])) { dependents.put(dep[0], new ArrayList<>()); } dependents.get(dep[0]).add(dep[1]); dependencyNum.put(dep[1], dependencyNum.getOrDefault(dep[1], 0) + 1); } for (int i = 0; i < jobs.size(); i++) { if (!dependencyNum.containsKey(jobs.get(i))) { q.offer(jobs.get(i)); } } while (!q.isEmpty()) { int currentJob = q.poll(); result.add(currentJob); List<Integer> currentJobDependents = dependents.get(currentJob); if (currentJobDependents != null) { for (Integer job : currentJobDependents) { dependencyNum.put(job, dependencyNum.get(job) - 1); if (dependencyNum.get(job) == 0) { q.offer(job); dependencyNum.remove(job); } } } } return dependencyNum.isEmpty() ? result : new ArrayList<Integer>(); } }
|