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

01 Course Schedule

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

const courseSchedule = (numCourses, prerequisites) => {
  let map = {}
  const adj = [...Array(numCourses)].map(r => [])
  for (let [u, v] of prerequisites) {
    adj[v].push(u)
  }
  let visitedSet = new Set()
  const dfs = e => {
    if (visitedSet.has(e)) {
      return false
    }
    if (adj[e].length == 0) {
      return true
    }
    visitedSet.add(e)
    for (const c of adj[e]) {
      if (!dfs(c)) {
        return false
      }
    }
    visitedSet.delete(e)
    adj[e] = []
    return true
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) {
      return false
    }
  }
  return true
}

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

Created 2022-02-09T01:17:13+00:00, updated 2022-02-09T17:22:10+00:00 · History · Edit