Topological Sort

• j+d, j+d
• v+e, v+e

function topologicalSort(jobs, deps) {
  const answer = ();
  // create adj list for each job
  const adj = {};
  for (let i = 0; i < jobs.length; i++) {
    const job = jobs(i);
    if (adj(job) === undefined) 
      adj(job) = ();
  }

  // form a adj list
  // count edges directing there
  const inCommingEdges = {};
  for (let i = 0; i < deps.length; i++) {
    const (here, there) = deps(i);
    adj(here).push(there);

    if (inCommingEdges(there) === undefined) 
      inCommingEdges(there) = 0;
    inCommingEdges(there) += 1;
  }

  // pick all edges, which has no incomming edges
  const q = ();
  for (const (here, edges) of Object.entries(adj)) {
    if (inCommingEdges(here) > 0) continue;
    q.push(here);
  }

  // use bfs to search toplogical sort
  while (q.length > 0) {
    const here = q.shift();
    for (const there of adj(here)) {
      inCommingEdges(there)--;
      if (inCommingEdges(there) > 0) continue;
      q.push(there);
    }
    answer.push(here);
  }

  console.log({
    answer
  });

  return answer.length === jobs.length ? answer : ();
}

// not working with dfs
// function dfs(adj, visited, here, order) {
//   visited(here) = 1;

//   for (let i = 0; i < adj(here).length; i++) {
//     const there = adj(here)(i);
//     if (visited(there) !
== 0) continue;

//     // if (visited(there) === 1) continue;
//     dfs(adj, visited, there, order);
//   }

//   visited(here) = 2;
// }
// Do not edit the line below.
exports.topologicalSort = topologicalSort;