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

Find Critical and Pseudo-Critical Edges in MST

Problem (yeniden ifade)

Ağırlıklı yönsüz graf. [critical, pseudoCritical] — kenar indeksleri. Critical: silince MST ağırlığı artar (veya kopar). Pseudo-critical: critical değil ama bazı MST onu içerir.

Sezgi

n ≤ 100, her kenar için Kruskal’ı tekrar çalıştır. Taban ağırlık base. i’yi hariç tut: maliyet > base → critical. i’yi önce zorla: maliyet == base ve critical değil → pseudo.

Yaklaşımlar

Kruskal, zorla / hariç tut

Doğrulanmadı

Zaman O(E² α(n))Alan O(n)

Fikir. Her kenara orijinal indeksini tak, kopyayı sırala. mst(exclude, force) varsa zorlanan kenarı önce birleştirir, sonra sıralı listede hariç tutulan indeksi atlar. Kopuk → ∞.

Yürüyüş. Beş köşe, 1/2/3 ağırlıklı kenarlar: iki ağırlık-1 kenar tek köprü (critical); birkaç 2/3 kenar alternatif MST’lerde (pseudo).

Trade-off. Orijinal indeksleri koru — cevap uçlar değil. Daha ucuz bir döngüyü kapatan kenarı zorlamak > base üretir, o yüzden ne critical ne pseudo.

Çözüm

export function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
  const indexed = edges.map((e, i) => [e[0]!, e[1]!, e[2]!, i]);
  indexed.sort((a, b) => a[2]! - b[2]!);

  const mst = (exclude: number, force: number): number => {
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
    let cost = 0, used = 0;
    const uni = (u: number, v: number, w: number): boolean => {
      const a = find(u), b = find(v);
      if (a === b) return false;
      parent[a] = b;
      cost += w;
      used++;
      return true;
    };
    if (force >= 0) {
      const e = edges[force]!;
      uni(e[0]!, e[1]!, e[2]!);
    }
    for (const e of indexed) {
      if (e[3] === exclude || e[3] === force) continue;
      uni(e[0]!, e[1]!, e[2]!);
      if (used === n - 1) break;
    }
    return used === n - 1 ? cost : Infinity;
  };

  const base = mst(-1, -1);
  const critical: number[] = [];
  const pseudo: number[] = [];
  for (let i = 0; i < edges.length; i++) {
    if (mst(i, -1) > base) critical.push(i);
    else if (mst(-1, i) === base) pseudo.push(i);
  }
  return [critical, pseudo];
}

export function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
  const indexed = edges.map((e, i) => [e[0]!, e[1]!, e[2]!, i]);
  indexed.sort((a, b) => a[2]! - b[2]!);

  const mst = (exclude: number, force: number): number => {
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
    let cost = 0, used = 0;
    const uni = (u: number, v: number, w: number): boolean => {
      const a = find(u), b = find(v);
      if (a === b) return false;
      parent[a] = b;
      cost += w;
      used++;
      return true;
    };
    if (force >= 0) {
      const e = edges[force]!;
      uni(e[0]!, e[1]!, e[2]!);
    }
    for (const e of indexed) {
      if (e[3] === exclude || e[3] === force) continue;
      uni(e[0]!, e[1]!, e[2]!);
      if (used === n - 1) break;
    }
    return used === n - 1 ? cost : Infinity;
  };

  const base = mst(-1, -1);
  const critical: number[] = [];
  const pseudo: number[] = [];
  for (let i = 0; i < edges.length; i++) {
    if (mst(i, -1) > base) critical.push(i);
    else if (mst(-1, i) === base) pseudo.push(i);
  }
  return [critical, pseudo];
}

Şablon bağlantısı

Alt yordam olarak Kruskal. LC 1135 ile aynı UF, filtreyle O(E) kez.

Yansıma

Önce taban MST. Kenarı çıkar: maliyet artar veya koparsa kritik. Zorla ve maliyet aynıysa, kritik değilse sözde kritik.
İkisi birden yazılmaz. Daha ucuz bir döngüyü kapatan kenar ne kritik ne sözde.
Kopuk sonuç sonsuz. Cevap uçlar değil, orijinal kenar indeksi. n = 1 kenar yok.