Trgovec

Osnovne informacije

Omejitve
  • Čas: 3 s
  • Spomin: 256 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2017

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Potujoči trgovec se je znašel v enosmernem kraljestvu. Tu kraljujejo enosmerni kolovozi, ki povezujejo vasi med seboj. Trgovec je prepričan, da se nekje v kraljestvu skriva kupec, ki ga bo odrešil finančnih skrbi. Zato želi obiskati vsako vas vsaj enkrat. Vasi so oštevilčene z zaporednimi celimi števili od 1 do N. Trenutno se nahaja v vasi S. Napišite program, ki bo ugotovil, ali lahko trgovec doseže svoj cilj (tj. ali lahko vsako vas obišče vsaj enkrat).

Vhodni podatki

V prvi vrstici se nahajajo tri cela števila, ki so ločena s presledki: število vasi N, število cest med vasmi M in zaporedna številka vasi S, v kateri se trgovec trenutno nahaja.

Sledi M vrstic s pari števil A_i in B_i. Tak par predstavlja kolovoz od vasi A_i proti vasi B_i. Med istim parom vasi je lahko tudi več kolovozov, prav tako pa lahko kolovoz vodi iz vasi nazaj v isto vas.

Omejitve vhodnih podatkov

  • 1 \leq N, M \leq 100\,000
  • 1 \leq S, A_i, B_i \leq N

Izhodni podatki

Če trgovec lahko obišče vse vasi, naj program izpiše DA, v nasprotnem primeru pa naj izpiše NE.

Primeri

Vhod

3 2 1
1 2
1 3

Izhod

NE

Vhod

3 3 1
1 2
1 3
3 2

Izhod

DA

Komentar

Prvi primer prikazuje naslednja slika:

alt text

Če trgovec odpotuje v vas 3, ne bo mogel obiskati vasi 2 (in obratno).

Drugi primer prikazuje naslednja slika:

alt text

Trgovec lahko najprej potuje v vas 3, nato pa v vas 2. Vasi 1 (kjer je bil na začetku) mu ni potrebno ponovno obiskati.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task