Topological sort for undirected graph.

topologicalSortForUndirectedGraph.ts

function topologicalSort(n: number, edges: number[][]): number[] {
  const numberOfEdges = Array(n).fill(0);
  const bidirectionalEdges: number[][] = [];
  for (let i = 0; i < n; i++) {
    bidirectionalEdges.push([]);
  }
  const sorted: number[] = [];
  // Construct the # of edges dictionary
  for (const [nodeA, nodeB] of edges) {
    numberOfEdges[nodeA]++;
    numberOfEdges[nodeB]++;
    bidirectionalEdges[nodeA].push(nodeB);
    bidirectionalEdges[nodeB].push(nodeA);
  }
  const leaves: number[] = [];
  for (let i = 0; i < n; i++) {
    if (numberOfEdges[i] == 1)
      leaves.push(i);
  }
  while (leaves.length > 0) {
    const leaf = leaves.pop();
    sorted.push(leaf);
    const connectedNodes = bidirectionalEdges[leaf];
    for (const connectedNode of connectedNodes) {
      if (numberOfEdges[connectedNode] === 0)
        continue;
      numberOfEdges[connectedNode]--;
      numberOfEdges[leaf]--;
      if (numberOfEdges[connectedNode] === 1) {
        leaves.push(connectedNode);
      }
    }
  }
  return sorted;
}