code.ashish.me

Atom feed

Recently added: 02 Count Of Subset Sum, 416 Partition Equal Subset Sum, 01 Subset Sum, 518 Coin Change 2, 983 Minimum Cost For Tickets

02 Course Schedule 2

/**
 *
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

const courseSchedule2 = (numCourses, prerequisites) => {
  let adj = {}
  for (let i = 0; i < numCourses; i++) {
    adj[i] = []
  }
  for (let [v, e] of prerequisites) {
    adj[v].push(e)
  }
  let cycle = new Set()
  let visited = new Set()
  let output = []
  const dfs = node => {
    if (cycle.has(node)) {
      return false
    }
    if (visited.has(node)) {
      return true
    }
    cycle.add(node)
    for (const v of adj[node]) {
      if (!dfs(v)) {
        return false
      }
    }
    cycle.delete(node)
    visited.add(node)
    output.push(node)
    return true
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) {
      return []
    }
  }
  return output
}

console.log(courseSchedule2(2, [[1, 0]]))

Created 2022-02-10T05:45:44+00:00 · Edit