Fazlalık bağlantı

Problem

1..n numaralı düğümlerden oluşan bir ağaca (bağlı ve döngüsüz yönsüz graf) fazladan bir kenar eklenmiş; sonuçta n düğümlü, n kenarlı bir graf elde edilmiş. Kenarlar {a, b} listesi olarak veriliyor. Çıkarıldığında geriye yine n düğümlü bir ağaç kalacak bir kenar döndür. Birden fazla aday varsa listede en son geçeni döndür.

Kenarlar: [{1, 2}, {1, 3}, {2, 3}]

  1
 / \
2 - 3

Üç kenar da döngüde; en son gelen {2, 3}.   Çıktı: [2, 3]

Kenarlar: [{1, 2}, {2, 3}, {3, 4}, {4, 2}, {1, 5}]

Döngü 2-3-4-2. Döngüdeki kenarlardan listede en son gelen {4, 2}.   Çıktı: [4, 2]

Netleştirme soruları

• Graf yönsüz mü? (Evet. Yönlü versiyonu, Redundant Connection II, çok daha zordur.)
• Fazlalık kenar tam olarak bir tane mi? (Evet; dolayısıyla grafta tam bir döngü var.)
• Aynı kenar iki kez tekrarlanabilir mi? (LeetCode'da hayır, ama tekrar ederse ikinci kopya cevap olur ve çözüm bunu doğal olarak verir.)
• "En son geçen" kuralı neden önemli? (Döngüdeki her kenar geçerli bir cevaptır; kural cevabı tekil yapar.)

İpuçları

Yaklaşım

Kaba çözüm: Kenarları sondan başa dene; her birini çıkarıp kalan grafın ağaç olup olmadığını (bağlı ve n - 1 kenarlı) DFS ile kontrol et. İlk başarılı olan cevaptır. O(n²). Test kodunda referans olarak bu kullanıldı.

DFS ile artımlı kontrol: Her kenar eklemeden önce a'dan b'ye mevcut kenarlarla ulaşılabiliyor mu diye DFS yap. Ulaşılabiliyorsa bu kenar cevaptır. O(n²).

Union-Find (optimal): "a ve b zaten bağlı mı?" sorusu Union-Find'ın find(a) == find(b) işlemidir. Kenarları sırayla işleriz: kökler farklıysa birleştiririz, aynıysa bu kenar döngüyü kapatır ve cevaptır.

"En son geçen" neden kendiliğinden sağlanıyor? Graf tek bir döngü içerir. Kenarları sırayla eklerken döngü ancak döngünün son kenarı eklendiğinde kapanır; döngünün diğer kenarları ondan önce eklenmiş ve hiçbiri tek başına döngü oluşturmamıştır. Dolayısıyla union'ın ilk başarısız olduğu kenar, döngü kenarları arasında listede en sonda geçendir; ve sadece döngü kenarları geçerli cevaplardır (döngü dışındaki bir kenarı çıkarmak grafı ikiye böler).

Java çözümü

public final class RedundantConnection {

    /** Düğümler 1..n; tam olarak bir fazlalık kenar var. */
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;                             // n düğüm, n kenar
        int[] parent = new int[n + 1];
        int[] size = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int[] edge : edges) {
            int rootA = find(parent, edge[0]);
            int rootB = find(parent, edge[1]);
            if (rootA == rootB) return edge;              // iki uç zaten bağlı: bu kenar döngüyü kapatıyor
            if (size[rootA] < size[rootB]) {
                int tmp = rootA; rootA = rootB; rootB = tmp;
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        throw new IllegalArgumentException("graph has no cycle");
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

Düğümler 1'den başladığı için diziler n + 1 boyutunda açıldı; 0. indeks kullanılmıyor. Bu, -1 dönüşümleriyle uğraşmaktan daha az hata riski taşır. Döngü bulunamazsa (girdi sözleşmesi ihlal edilmişse) sessizce null dönmek yerine exception fırlatılıyor.

Karmaşıklık

• Zaman: O(n · α(n)), pratikte O(n). Her kenar için iki find ve en fazla bir birleştirme.
• Bellek: O(n) ebeveyn ve boyut dizileri.

Kenar durumlar ve testler

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

• Üçgen: [2, 3] (en son gelen döngü kenarı).
• Kare + kuyruk ([{1,2},{2,3},{3,4},{1,4},{1,5}]): [1, 4]; döngüden sonra gelen {1, 5} cevap değil.
• 1 numaralı düğümden geçmeyen döngü: [4, 2].
• 2.000 rastgele girdi: rastgele bir ağaca rastgele bir fazla kenar eklenip kenar sırası karıştırıldı; sonuç "sondan başa çıkar, ağaç kaldı mı bak" kaba çözümüyle karşılaştırıldı.

Mülakatçı için

Bu soru Union-Find'ın "döngü tespiti" kullanımını ölçer. Güçlü aday "en son geçen" kuralının neden ekstra bir iş gerektirmediğini kanıtlayabilir; bu, çözümü ezberden değil anlayarak yazdığını gösterir. Zayıf aday tüm döngü kenarlarını bulup sonra en sondakini seçmeye çalışır; çalışır ama gereksiz karmaşıktır.

İpucu zamanlaması: Aday DFS ile artımlı çözümü önerirse yazmasına izin ver, sonra "her kenar için DFS yapmadan bunu hızlandırabilir miyiz?" diye sor. İkinci ipucunu Union-Find'ı bilmeyen adaya kavramı tanıtmak için kullan. Üçüncü ipucundaki "neden en sondaki" sorusunu ipucu olarak değil, değerlendirme sorusu olarak sormak daha faydalıdır.

Takip sorusu 1: Graf yönlü olsaydı (köklü ağaç + bir fazla kenar)? Beklenen: iki durum var: bir düğümün iki ebeveyni olabilir ya da döngü oluşur ya da ikisi birden. Önce iki ebeveynli düğümü tespit edip aday kenarları ayırmak, sonra Union-Find ile döngü kontrolü (LeetCode 685, Zor).

Takip sorusu 2: Fazlalık kenar sayısı k olsaydı ve en az kenarı çıkararak ağaç elde etmek isteseydin? Beklenen: Union-Find ile başarısız tüm birleştirmeleri toplamak; bunların sayısı tam olarak E - (n - 1)'dir (bağlı graf varsayımıyla). Bu aslında bir yayılan ağaç (spanning tree) inşasıdır; ağırlıklı versiyonu Kruskal'dır.

Takip sorusu 3: Bir ağ topolojisinde (switch'ler ve kablolar) döngüye yol açan kabloyu bulmak gerçek hayatta neyle yapılır? Beklenen: Spanning Tree Protocol'ün amacı tam olarak budur; döngü oluşturan bağlantıları bloklar. Algoritmik olarak aynı fikir: yayılan ağaç dışındaki kenarlar fazlalıktır.

Benzer problemler

• Redundant Connection II (LeetCode 685)
• Graph Valid Tree (LeetCode 261)
• Number of Provinces (LeetCode 547)
• Min Cost to Connect All Points (LeetCode 1584)
• Number of Operations to Make Network Connected (LeetCode 1319)