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

Mediumminimum-spanning-tree

Connecting Cities With Minimum Cost

Problem (yeniden ifade)

n şehir 1…n ve çift yönlü bağlantılar [x, y, cost]. Tüm şehirleri bağlamanın minimum maliyetini döndür; imkânsızsa -1.

Sezgi

Tüm şehirleri minimum toplam maliyetle bağla — bu bir MST. Kruskal: kenarları sırala, union-find döngüleri atlar, n-1 kenarda dur.

Yaklaşımlar

Kruskal

Doğrulanmadı

Zaman O(E log E)Alan O(n)

Fikir. Maliyete göre sırala. Uçlar bağlı değilse birleştir. n-1 kenar aldıysan toplam cevaptır; kalan bileşen → -1.

Yürüyüş. n=3, [[1,2,5],[1,3,6],[2,3,1]]. 2-3 (1), sonra 1-2 (5). Toplam 6. 1-3 döngü.

Trade-off. Şehirler 1-indeksli — parent dizisi n+1. Prim aynı MST, yoğun grafta; burada E açıkça verilmiş.

Çözüm

export function minimumCost(n: number, connections: number[][]): number {
  const edges = [...connections].sort((a, b) => a[2]! - b[2]!);
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) continue;
    parent[a] = b;
    cost += e[2]!;
    used++;
    if (used === n - 1) return cost;
  }
  return -1;
}

export function minimumCost(n: number, connections: number[][]): number {
  const edges = [...connections].sort((a, b) => a[2]! - b[2]!);
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) continue;
    parent[a] = b;
    cost += e[2]!;
    used++;
    if (used === n - 1) return cost;
  }
  return -1;
}

Şablon bağlantısı

Düz Kruskal. LC 1584 önce Manhattan çiftlerinden kenar listesi üretir; LC 1168 sanal kuyu düğümü ekler.

Yansıma

Kenarları maliyete göre sırala. Union-Find. n−1 kenar bağlanmazsa −1.
Aynı köke düşen kenar döngüdür, atlanır. Eşit maliyette sıra toplamı değiştirmez.
n = 1 cevap 0. Kopuk şehir −1. MST maliyeti kenarların toplamı.