İl sayısı: bağlı bileşenler

Problem

n şehir var. n x n boyutlu bir isConnected matrisi veriliyor: isConnected[i][j] == 1 ise i ve j şehirleri doğrudan yolla bağlı. Bağlantı geçişlidir: a, b'ye ve b, c'ye bağlıysa a ile c aynı ildedir. Birbirine doğrudan ya da dolaylı bağlı şehirlerin oluşturduğu grup sayısını (il sayısını) döndür.

     0  1  2
0 [  1, 1, 0 ]
1 [  1, 1, 0 ]
2 [  0, 0, 1 ]

Çıktı: 2   ({0, 1} ve {2})

     0  1  2  3
0 [  1, 0, 0, 1 ]
1 [  0, 1, 1, 0 ]
2 [  0, 1, 1, 1 ]
3 [  1, 0, 1, 1 ]

Çıktı: 1   (0-3, 3-2, 2-1 üzerinden hepsi bağlı)

Netleştirme soruları

• Matris simetrik mi ve köşegen hep 1 mi? (Evet; yollar iki yönlü.)
• n ne kadar büyük? (Matris girdisi zaten O(n²); n en fazla birkaç yüz.)
• Bağlantılar sonradan eklenecek mi? (Eklenecekse Union-Find dolaşıma göre çok daha avantajlı.)
• Girdi matris değil kenar listesi olsaydı? (Karmaşıklık O(n²) yerine O(n + E) olurdu.)

İpuçları

Yaklaşım

Problem, yönsüz grafta bağlı bileşen sayısıdır. İki standart yol var.

DFS/BFS: Her ziyaret edilmemiş şehirden dolaşım başlat, sayacı artır. Matris girdisinde her şehrin komşularını bulmak için satırın tamamını taramak gerekir; toplam O(n²). Bu problem için tamamen yeterli ve doğru bir cevaptır.

Union-Find (Disjoint Set Union, seçilen çözüm): Her düğüm bir ebeveyn işaretçisi tutar; kökü kendisini gösteren düğüm kümenin temsilcisidir.

• find(x): x'ten köke çıkar. Path compression yol üzerindeki düğümleri köke yaklaştırır; aşağıdaki çözüm "path halving" varyantını kullanır (her düğümü büyük ebeveynine bağlar), tek döngüyle ve özyinelemesiz.
• union(a, b): iki kökü bulur; farklıysa küçük kümenin kökünü büyüğün köküne bağlar (union by size). Böylece ağaç yüksekliği O(log n) ile sınırlı kalır.

İki optimizasyon birlikte kullanıldığında işlem başına amortize maliyet O(α(n))'dir; α ters Ackermann fonksiyonudur ve pratikte 5'ten küçüktür. Sadece birini kullanmak O(log n) verir.

Union-Find'ın bu soruda dolaşıma göre asimptotik avantajı yoktur (matris okumak zaten O(n²)). Asıl değeri, kenarlar çevrimiçi geldiğinde ortaya çıkar: her yeni yol için grafı yeniden dolaşmadan bileşen sayısı güncellenir. Mülakatta Union-Find'ı bu gerekçeyle seçmek, "sadece ezberden" seçmekten iyidir.

Java çözümü

public final class NumberOfProvinces {

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {            // matris simetrik: üst üçgen yeterli
                if (isConnected[i][j] == 1) uf.union(i, j);
            }
        }
        return uf.components();
    }

    private static final class UnionFind {
        private final int[] parent;
        private final int[] size;
        private int components;

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
            components = n;                               // başta herkes kendi kümesi
        }

        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];            // path halving: yolu yarıya kısalt
                x = parent[x];
            }
            return x;
        }

        boolean union(int a, int b) {
            int rootA = find(a), rootB = find(b);
            if (rootA == rootB) return false;             // zaten aynı küme
            if (size[rootA] < size[rootB]) {              // union by size: küçük ağacı büyüğe as
                int tmp = rootA; rootA = rootB; rootB = tmp;
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            components--;
            return true;
        }

        int components() { return components; }
    }
}

Matrisin sadece üst üçgeni gezilir; simetrik olduğu için alt üçgen aynı birleştirmeleri tekrar ederdi (sonuç değişmezdi, ama iş iki katına çıkardı). UnionFind iç sınıfı genel amaçlıdır; aynı sınıf Redundant Connection ve Number of Islands II gibi sorularda olduğu gibi kullanılır.

Karmaşıklık

• Zaman: O(n² · α(n)), pratikte O(n²). Matrisin yarısı okunur; her birleştirme amortize O(α(n)).
• Bellek: O(n) ebeveyn ve boyut dizileri. DFS çözümünde O(n) ziyaret dizisi ve stack.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• İlk örnek: 2. Birim matris (hiç yol yok): 3.
• Tek şehir: 1.
• Geçişli bağlantı (ikinci örnek): 1. Doğrudan bağlı olmayan 0 ve 1'in aynı ilde olduğunu doğrular.
• 2.000 rastgele simetrik matris (1-12 şehir), iteratif DFS ile bileşen sayan referansla karşılaştırıldı.

Mülakatçı için

Bu soru Union-Find'ı tanıtmak için klasik bir giriştir. DFS ile çözen adayı eksik sayma; çözüm optimaldir. Ardından "yollar tek tek eklenseydi ve her eklemeden sonra il sayısını soruyor olsaydım?" diye sorarak Union-Find'a geçişi gözlemle. Union-Find yazan adayda find'ın path compression'ını ve union'ın başarılı olup olmadığını döndürmesini kontrol et; sayaç ancak başarılı birleştirmede azalmalıdır.

İpucu zamanlaması: Aday bağlı bileşen fikrine 3 dakikada ulaşamazsa ilk ipucunu ver. Union-Find istiyorsan ama aday bilmiyorsa, ikinci ipucunu verip temel yapıyı birlikte kurmak bile değerli bir sinyal üretir: yeni bir veri yapısını ne kadar hızlı kavradığını görürsün.

Takip sorusu 1: Union-Find'a "iki kümeyi ayır" (kenar silme) işlemi ekleyebilir misin? Beklenen: Klasik Union-Find silmeyi desteklemez. Silmeler biliniyorsa işlemleri tersten oynatıp silmeyi eklemeye çevirmek (offline), ya da her silmede ilgili bileşeni yeniden kurmak.

Takip sorusu 2: Girdi 10 milyon kullanıcı ve 100 milyon arkadaşlık kenarı; aynı "topluluk" sayısını bul. Beklenen: matris yerine kenar listesi, int[] tabanlı Union-Find (nesne başına overhead yok), kenarları stream ederek tek geçiş; bellek O(n). Dağıtık ortamda bağlı bileşen için iteratif etiket yayma (label propagation) algoritmaları.

Takip sorusu 3: Bir banka müşteri verisinde aynı kişiye ait kayıtları (ortak telefon, e-posta ya da kimlik bilgisiyle) gruplayacaksın. Beklenen: her ortak alan değerini bir "köprü" sayıp kayıtları birleştirmek (Accounts Merge, LeetCode 721); alan değeri -> ilk kayıt haritası ile O(toplam alan) birleştirme.

Benzer problemler

• Redundant Connection (LeetCode 684)
• Number of Connected Components in an Undirected Graph (LeetCode 323)
• Accounts Merge (LeetCode 721)
• Graph Valid Tree (LeetCode 261)
• Number of Islands (LeetCode 200)