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-dfs

Number of Provinces

Problem (yeniden ifade)

isConnected matrisli n şehir. Bir province bağlı bir gruptur. Province sayısını döndür.

Sezgi

Bağlı çiftleri birleştir; cevap bileşen sayısıdır.

Yaklaşımlar

Union-Find

Doğrulanmadı

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

Fikir. matrix[i][j]==1 iken i-j üzerinde UF.

Yürüyüş. Tam bağlı → 1 province.

Trade-off. UF vs matriste DFS flood.

Çözüm

export function findCircleNum(isConnected: number[][]): number {
  const n = isConnected.length;
  const p = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (p[x] === x ? x : (p[x] = find(p[x]!)));
  let comp = n;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i]![j] === 1) {
        const a = find(i), b = find(j);
        if (a !== b) {
          p[b] = a;
          comp--;
        }
      }
    }
  }
  return comp;
}

export function findCircleNum(isConnected: number[][]): number {
  const n = isConnected.length;
  const p = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (p[x] === x ? x : (p[x] = find(p[x]!)));
  let comp = n;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i]![j] === 1) {
        const a = find(i), b = find(j);
        if (a !== b) {
          p[b] = a;
          comp--;
        }
      }
    }
  }
  return comp;
}

Şablon bağlantısı

Union-Find bileşenleri.

Yansıma

isConnected[i][j] == 1 ise birleştir. Cevap kalan bileşen. Köşegen kendisi.
Aynı köke ikinci kez union bileşeni azaltmaz. Matris simetrik.
n = 1 cevap 1. Kenar yok cevap n. Hepsi bağlı cevap 1.