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>();
}
}
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>();
}
}