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

Mediumunion-find

Graph Valid Tree

Problem (yeniden ifade)

0..n-1 etiketli n düğüm ve yönsüz kenarlar. Geçerli bir ağaç oluşturuyorlarsa true döndür (bağlı, döngüsüz).

Sezgi

n düğümlü bir ağacın tam n-1 kenarı vardır ve bağlıdır. Union-Find, zaten birleşmiş düğümleri birleştiren her kenarı reddeder (döngü).

Yaklaşımlar

Union-Find + kenar sayısı

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. edges.length != n-1 ise başarısız. Her kenarı birleştir; gereksiz bağlantıda false. n-1 başarılı union ile graf bağlıdır.

Yürüyüş. n=5, edges=[[0,1],[0,2],[0,3],[1,4]] → true; [1,2] eklemek döngü yapardı.

Trade-off. 0’dan BFS/DFS da çalışır; UF işlem başına O(α(n)).

Çözüm

export function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) return false;
    parent[b] = a;
  }
  return true;
}

export function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) return false;
    parent[b] = a;
  }
  return true;
}

Şablon bağlantısı

Döngü tespiti + bağlılık için Union-Find.

Yansıma

n düğüm ve n−1 kenar yetmez; tek bileşen de şart. Fazla kenar döngü, eksik kenar orman.
union aynı köke düşerse döngü var. Sonda bileşen sayısı 1 mi?
n = 1 ve kenar yok: ağaç. İki düğüm kenarsız: değil. Kendine kenar döngü.