K24
Grafikte Yol Var mı?
Teknik Tanım & Görev
0'dan n-1'e kadar numaralanmış n adet düğüm ve bu düğümleri bağlayan iki yönlü kenarlar verilmiştir. 'kaynak' düğümünden başlayarak 'hedef' düğümüne ulaşan en az bir geçerli yol olup olmadığını belirleyiniz.
n, 2*10^5'e kadar çıkabilir. Düz özyinelemeli DFS, Python'un varsayılan çağrı sınırında çöker. BFS veya açık yığın kullanın.
Fonksiyon İmzası (Python)
yol_var_mi(n: int, kenarlar: list[list[int]], kaynak: int, hedef: int) -> boolGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:True veya False.
Sistem Kısıtları (Constraints)
1 <= n <= 2 * 10^5
0 <= kenarlar.length <= 2 * 10^5
0 <= kaynak, hedef < nÖrnek Yürütme Analizi
n = 3, kenarlar = [[0, 1], [1, 2], [2, 0]], kaynak = 0, hedef = 2 -> TrueÖrnek Test Senaryoları (3)
Örnek 1: Üçgen Yol
Girdi:
[3,[[0,1],[1,2],[2,0]],0,2]Beklenen Çıktı:
trueÖrnek 2: Ayrık Bileşenler
Girdi:
[6,[[0,1],[0,2],[3,5],[5,4],[4,3]],0,5]Beklenen Çıktı:
falseÖrnek 3: Tek Düğüm
Girdi:
[1,[],0,0]Beklenen Çıktı:
true