Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtopological-sort

Course Schedule

Problem (yeniden ifade)

n ders, [a,b] önkoşul çiftleri b’nin a’dan önce geldiği anlamına gelir. Hepsini bitirip bitiremeyeceğini döndür.

Sezgi

Yönlü grafte topo sort ile döngü tespit et; sıra uzunluğu < n ise döngü.

Yaklaşımlar

Kahn BFS

Doğrulanmadı

Zaman O(V+E)Alan O(V+E)

Fikir. Indegree kuyruğu Kahn; alınan dersleri say.

Yürüyüş. [[1,0]] n=2 → true; cycle → false.

Trade-off. Kahn vs DFS renkleri.

Çözüm

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    g[b!]!.push(a!);
    indeg[a!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let taken = 0;
  while (q.length) {
    const u = q.shift()!;
    taken++;
    for (const v of g[u]!) {
      if (--indeg[v]! === 0) q.push(v);
    }
  }
  return taken === numCourses;
}

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    g[b!]!.push(a!);
    indeg[a!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let taken = 0;
  while (q.length) {
    const u = q.shift()!;
    taken++;
    for (const v of g[u]!) {
      if (--indeg[v]! === 0) q.push(v);
    }
  }
  return taken === numCourses;
}

Şablon bağlantısı

Topological sort döngü tespiti.

Yansıma

Kenar önkoşuldan derse. Kahn: indegree 0 kuyruğa. Çıkan düğüm sayısı n değilse döngü, false.
[[0,1],[1,0]] döngü. Kenar yok: true. Aynı önkoşulu iki kez saymak indegree’yi şişirir.
DFS renkleriyle gri düğüme dönmek de döngüdür. İki yöntem aynı cevabı verir.