Z37
Ağda Kritik Bağlantılar - Köprü Tespiti
Teknik Tanım & Görev
n adet sunucudan oluşan bir iletişim ağında, kaldırıldığında sunucuların bir kısmının birbiriyle iletişimini koparan (grafiği ikiye bölen) tüm 'kritik bağlantıları' (köprüleri / bridge edges) bulunuz. Her kritik bağlantı [min(u, v), max(u, v)] formatında ve tüm liste sözlük sırasına göre sıralı dönmelidir.
Aynı {u, v} çifti birden fazla kez verilirse tek kenar sayılır. İki düğüm arasında gerçekten iki ayrı kenar varsa (paralel kenar) o kenar köprü değildir: biri kalkınca diğeri bağlantıyı tutar. Bu katalogda paralel çift, tekrarın tek kenara indirilmesiyle ele alınır; girdi tekrar etmezse her çift bir kenardır.
Derin özyineleme n = 10^5 iken Python'un varsayılan çağrı sınırını aşabilir. Yığın tabanlı DFS veya sınırı yükseltmek gerekir.
Fonksiyon İmzası (Python)
kritik_baglantilar(n: int, baglantilar: list[list[int]]) -> list[list[int]]Girdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Kritik bağlantılar listesi (sıralı).
Sistem Kısıtları (Constraints)
2 <= n <= 10^5
n - 1 <= baglantilar.length <= 10^5
0 <= u, v < n, u != v
Ağ başlangıçta tamamen bağlıdırÖrnek Yürütme Analizi
n = 4, baglantilar = [[0, 1], [1, 2], [2, 0], [1, 3]]
[1, 3] koparsa 3 izole olur -> cevap: [[1, 3]]Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[4,[[0,1],[1,2],[2,0],[1,3]]]Beklenen Çıktı:
[[1,3]]Örnek 2: Tek Hat
Girdi:
[2,[[0,1]]]Beklenen Çıktı:
[[0,1]]Örnek 3: Halka (Köprü Yok)
Girdi:
[3,[[0,1],[1,2],[2,0]]]Beklenen Çıktı:
[]