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

Redundant Connection

Problem (yeniden ifade)

n düğümlü bir ağaç olarak başlayan yönsüz graf; sonra bir fazla kenar eklenmiş. Döngü oluşturan o gereksiz kenarı döndür. Birden fazla cevap varsa girdide en son görüneni ver.

Sezgi

Kenarları sırayla Union-Find ile tara. Uç noktaları aynı kökte olan ilk kenar gereksiz olandır.

Yaklaşımlar

Union-Find ilk döngü kenarı

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. parent[1..n]. Her [u,v] için Find(u)==Find(v) ise kenarı döndür; değilse birleştir.

Adım adım. [[1,2],[1,3],[2,3]] → [2,3] üçgeni kapatır.

Trade-off’lar. “Son” şartı için girdi sırası önemli, soldan sağa işle.

Çözüm

export function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, 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 e;
    parent[b] = a;
  }
  return [];
}

export function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, 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 e;
    parent[b] = a;
  }
  return [];
}

Şablon bağlantısı

Union-Find döngü tespiti.

Yansıma

Kenarları sırayla birleştir. İlk kez aynı köke düşen kenar fazlalık. Bu, döngüdeki herhangi kenar değil, listedeki ilkidir.
Ağaç artı bir kenar (garanti). Birden fazla aday varsa giriş sırası hangisini seçer?
Kendine kenar hemen döngü. Döngüsüz tek kenar fazlalık değildir.