/
index.ts
33 lines (27 loc) · 938 Bytes
/
index.ts
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
export default function canFinish(
numCourses: number,
prerequisites: number[][],
): boolean {
const dependents: Map<number, number[]> = new Map();
const indegress: Map<number, number> = new Map();
for (const [child, parent] of prerequisites) {
const array = dependents.get(parent) ?? [];
array.push(child);
dependents.set(parent, array);
indegress.set(child, (indegress.get(child) ?? 0) + 1);
}
const queue: number[] = Array.from(Array(numCourses).fill(0).keys()).filter(
(i) => !indegress.has(i),
);
let result: number = 0;
while (queue.length) {
const u = queue.shift() as number;
result++;
for (const v of dependents.get(u) ?? []) {
const degree = (indegress.get(v) ?? 0) - 1;
indegress.set(v, degree);
if (degree === 0) queue.push(v);
}
}
return result === numCourses;
}