K24

Grafikte Yol Var mı?

Temel Seviye (Junior)
Hedef Süre: 15 - 20 Dakika
Tip: BOOLEAN

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) -> bool

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