Tugas · algoritma sulit Python ·

Course order

def course_order(n: int, prereqs: list[list[int]]) -> list[int]:

course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])  # -> [0, 1, 2, 3]
course_order(2, [[0, 1], [1, 0]])  # -> []
course_order(3, [])  # -> [0, 1, 2]

• #1OpenAI GPT-6 Lunaselesai · 11 dari 11 pengujianrespons dalam 2.0 dtk · waktu eksekusi 587 md · $0.0001

  ✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])diharapkan [0, 1, 2, 3]	1 md
  ✓	course_order(2, [[0, 1], [1, 0]])diharapkan []	<1 md
  ✓	course_order(3, [])diharapkan [0, 1, 2]	<1 md

  ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 581 md
  Kode

  import heapq
  
  def course_order(n: int, prereqs: list[list[int]]) -> list[int]:
      graph = [[] for _ in range(n)]
      indegree = [0] * n
  
      for a, b in prereqs:
          graph[b].append(a)
          indegree[a] += 1
  
      ready = [i for i, degree in enumerate(indegree) if degree == 0]
      heapq.heapify(ready)
  
      order = []
      while ready:
          course = heapq.heappop(ready)
          order.append(course)
          for nxt in graph[course]:
              indegree[nxt] -= 1
              if indegree[nxt] == 0:
                  heapq.heappush(ready, nxt)
  
      return order if len(order) == n else []

• #1Z.ai GLM 5.3selesai · 11 dari 11 pengujianrespons dalam 901 md · waktu eksekusi 617 md · $0.0003

  ✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])diharapkan [0, 1, 2, 3]	<1 md
  ✓	course_order(2, [[0, 1], [1, 0]])diharapkan []	2 md
  ✓	course_order(3, [])diharapkan [0, 1, 2]	<1 md

  ✓ 2 md✓ 1 md✓ 2 md✓ <1 md✓ 2 md✓ 1 md✓ 1 md⏱ 604 md
  Kode

  import heapq
  
  def course_order(n: int, prereqs: list[list[int]]) -> list[int]:
      adj = [[] for _ in range(n)]
      indeg = [0] * n
      for a, b in prereqs:
          adj[b].append(a)
          indeg[a] += 1
      heap = [i for i in range(n) if indeg[i] == 0]
      heapq.heapify(heap)
      order = []
      while heap:
          u = heapq.heappop(heap)
          order.append(u)
          for v in adj[u]:
              indeg[v] -= 1
              if indeg[v] == 0:
                  heapq.heappush(heap, v)
      return order if len(order) == n else []

• #1Anthropic Claude Opus 5.5selesai · 11 dari 11 pengujianrespons dalam 6.1 dtk · waktu eksekusi 675 md · $0.01

  ✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])diharapkan [0, 1, 2, 3]	1 md
  ✓	course_order(2, [[0, 1], [1, 0]])diharapkan []	<1 md
  ✓	course_order(3, [])diharapkan [0, 1, 2]	<1 md

  ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ 11 md✓ <1 md⏱ 657 md
  Kode

  import heapq
  
  def course_order(n: int, prereqs: list[list[int]]) -> list[int]:
      if n <= 0:
          return []
      if not prereqs:
          return list(range(n))
      adj = [[] for _ in range(n)]
      indeg = [0] * n
      for a, b in prereqs:
          adj[b].append(a)
          indeg[a] += 1
      heap = [i for i in range(n) if indeg[i] == 0]
      heapq.heapify(heap)
      res = []
      push = heapq.heappush
      pop = heapq.heappop
      app = res.append
      while heap:
          u = pop(heap)
          app(u)
          for v in adj[u]:
              d = indeg[v] - 1
              indeg[v] = d
              if d == 0:
                  push(heap, v)
      return res if len(res) == n else []

• #1Qwen3 Coder Nextselesai · 11 dari 11 pengujianrespons dalam 3.9 dtk · waktu eksekusi 712 md · $0.0002

  ✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])diharapkan [0, 1, 2, 3]	1 md
  ✓	course_order(2, [[0, 1], [1, 0]])diharapkan []	<1 md
  ✓	course_order(3, [])diharapkan [0, 1, 2]	<1 md

  ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 706 md
  Kode

  import heapq
  from collections import defaultdict
  
  def course_order(n: int, prereqs: list[list[int]]) -> list[int]:
      # Build adjacency list and in-degree count
      graph = defaultdict(list)
      in_degree = [0] * n
      
      for a, b in prereqs:
          graph[b].append(a)
          in_degree[a] += 1
      
      # Min-heap to always get smallest available course
      heap = []
      for i in range(n):
          if in_degree[i] == 0:
              heapq.heappush(heap, i)
      
      result = []
      while heap:
          course = heapq.heappop(heap)
          result.append(course)
          
          for neighbor in graph[course]:
              in_degree[neighbor] -= 1
              if in_degree[neighbor] == 0:
                  heapq.heappush(heap, neighbor)
      
      # If we couldn't take all courses, there's a cycle
      if len(result) != n:
          return []
      
      return result

Biaya token: $0.01 · Cara babak dijalankan dan dinilai →