type Graph = Record<string, string[]>;

function topologicalSort(graph: Graph): string[] {
  // 时间复杂度: O(V + E)，空间复杂度: O(V + E) (V为顶点数，E为边数)
  const indegree: Record<string, number> = {};
  const queue: string[] = [];
  const result: string[] = [];

  Object.keys(graph).forEach((node) => {
    indegree[node] = indegree[node] ?? 0;
    for (const neighbor of graph[node]) {
      indegree[neighbor] = (indegree[neighbor] ?? 0) + 1;
    }
  });

  for (const node of Object.keys(indegree)) {
    if (indegree[node] === 0) queue.push(node);
  }

  while (queue.length) {
    const node = queue.shift()!;
    result.push(node);
    for (const neighbor of graph[node] ?? []) {
      indegree[neighbor] -= 1;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return result.length === Object.keys(indegree).length ? result : [];
}