Z37

Ağda Kritik Bağlantılar - Köprü Tespiti

Başmühendis (Staff/Lead)
Hedef Süre: 40 - 50 Dakika
Tip: ARRAY

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ı:[]
Python Editörü Yükleniyor...
Girdi Parametreleri
[
  4,
  [
    [
      0,
      1
    ],
    [
      1,
      2
    ],
    [
      2,
      0
    ],
    [
      1,
      3
    ]
  ]
]
Beklenen Çıktı
[
  [
    1,
    3
  ]
]