function topologicalSortBFS(numVertices, edges) {
  // Build adjacency list and in-degree array
  const graph    = Array.from({ length: numVertices }, () => []);
  const inDegree = new Array(numVertices).fill(0);

  for (const [u, v] of edges) {
    graph[u].push(v);
    inDegree[v]++;
  }

  // Queue: all vertices with no prerequisites
  const queue = [];
  for (let i = 0; i < numVertices; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order = [];
  while (queue.length > 0) {
    const node = queue.shift(); // O(n) — use a real queue for production
    order.push(node);
    for (const neighbour of graph[node]) {
      inDegree[neighbour]--;
      if (inDegree[neighbour] === 0) queue.push(neighbour);
    }
  }

  // Cycle detection: if order doesn't include all vertices, cycle exists
  return order.length === numVertices ? order : [];
}

// 5 courses, prerequisites: 1→0, 2→0, 3→1, 3→2, 4→3
const edges = [[1,0],[2,0],[3,1],[3,2],[4,3]];
console.log(topologicalSortBFS(5, edges)); // [0,1,2,3,4] or similar valid order

function topologicalSortDFS(numVertices, edges) {
  const graph = Array.from({ length: numVertices }, () => []);
  for (const [u, v] of edges) graph[u].push(v);

  const state = new Array(numVertices).fill(0); // 0=unvisited,1=visiting,2=done
  const order = [];
  let hasCycle = false;

  function dfs(node) {
    if (state[node] === 1) { hasCycle = true; return; } // back edge = cycle
    if (state[node] === 2) return;                        // already processed

    state[node] = 1; // mark as being visited
    for (const neighbour of graph[node]) {
      dfs(neighbour);
      if (hasCycle) return;
    }
    state[node] = 2;       // done
    order.unshift(node);   // prepend — post-order gives reverse topological sort
  }

  for (let i = 0; i < numVertices; i++) {
    if (state[i] === 0) dfs(i);
    if (hasCycle) return [];
  }
  return order;
}

const edges2 = [[1,0],[2,0],[3,1],[3,2],[4,3]];
console.log(topologicalSortDFS(5, edges2)); // [4,3,1,2,0] or similar

function canFinish(numCourses, prerequisites) {
  const graph    = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (const [course, pre] of prerequisites) {
    graph[pre].push(course);
    inDegree[course]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  let completed = 0;
  while (queue.length > 0) {
    const node = queue.shift();
    completed++;
    for (const next of graph[node]) {
      if (--inDegree[next] === 0) queue.push(next);
    }
  }
  return completed === numCourses;
}

console.log(canFinish(2, [[1,0]]));       // true  (take 0, then 1)
console.log(canFinish(2, [[1,0],[0,1]])); // false (cycle: 0↔1)

function findOrder(numCourses, prerequisites) {
  const graph    = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (const [course, pre] of prerequisites) {
    graph[pre].push(course);
    inDegree[course]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph[node]) {
      if (--inDegree[next] === 0) queue.push(next);
    }
  }
  return order.length === numCourses ? order : [];
}

console.log(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]));
// [0,1,2,3] or [0,2,1,3]

function alienOrder(words) {
  const graph    = new Map();
  const inDegree = new Map();

  // Initialise graph with all unique characters
  for (const word of words) {
    for (const ch of word) {
      if (!graph.has(ch))    graph.set(ch, new Set());
      if (!inDegree.has(ch)) inDegree.set(ch, 0);
    }
  }

  // Build edges from adjacent word comparisons
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    const minLen = Math.min(w1.length, w2.length);
    // Edge case: "abc" before "ab" is invalid
    if (w1.length > w2.length && w1.startsWith(w2)) return '';
    for (let j = 0; j < minLen; j++) {
      if (w1[j] !== w2[j]) {
        if (!graph.get(w1[j]).has(w2[j])) {
          graph.get(w1[j]).add(w2[j]);
          inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
        }
        break; // only first differing char matters
      }
    }
  }

  // Kahn's algorithm
  const queue = [];
  for (const [ch, deg] of inDegree) if (deg === 0) queue.push(ch);

  let result = '';
  while (queue.length > 0) {
    const ch = queue.shift();
    result += ch;
    for (const next of graph.get(ch)) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) queue.push(next);
    }
  }
  return result.length === inDegree.size ? result : '';
}

console.log(alienOrder(['wrt','wrf','er','ett','rftt'])); // 'wertf'