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`. ### Komentar Prvi primer prikazuje naslednja slika: ![alt text][1] Če trgovec odpotuje v vas 3, ne bo mogel obiskati vasi 2 (in obratno). Drugi primer prikazuje naslednja slika: ![alt text][2] 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. [1]: ?att=trgovec01.png [2]: ?att=trgovec02.png
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task