演算法

1function topologicalSort(n: number, edges: [number, number][]): number[] | null {
2  const out: number[][] = Array.from({ length: n }, () => []);
3  const indegree = new Array(n).fill(0);
4  for (const [u, v] of edges) {
5    out[u].push(v);
6    indegree[v]++;
7  }
8  for (const list of out) list.sort((a, b) => a - b);
9  const queue: number[] = [];
10  for (let v = 0; v < n; v++) {
11    if (indegree[v] === 0) queue.push(v);
12  }
13  const order: number[] = [];
14  for (let head = 0; head < queue.length; head++) {
15    const u = queue[head];
16    order.push(u);
17    for (const v of out[u]) {
18      indegree[v]--;
19      if (indegree[v] === 0) queue.push(v);
20    }
21  }
22  return order.length === n ? order : null;
23}