Prihlásenie Registrácia  

305 - Pn-vertex problem

Časový limit: 10s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3
Obtiažnosť: Stredná Stredná

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Cesta v grafe dĺžky n je postupnosť vrcholov a1,a2, ... ,an, taká, že medzi vrcholmi ai,ai+1 je hrana, a naviac, žiaden vrchol sa na ceste nesmie v ceste opakovať.
Hovoríme, že vrchol grafu je Pn-vertex, ak najdlhšia cesta, ktorá končí v tomto vrchole má dĺžku presne n.
Na obrázku môžete vidieť graf, v ktorom každý z vrcholov 1,2,6,7,8 je P8-vertex.

Uloha

Daný je graf G(V,E). V je množina vrcholov grafu ,E je množina jeho hrán. Dané je číslo n. Nájdite každý vrchol grafu, ktorý je Pn-vertex.

Vstup

Vstupný súbor bude obsahovať niekoľko sád vstupu oddelených prázdnym riadkom.
Prvý riadok bude obsahovašť 3 čísla: v,m,n. (0<v≤16), (n≤v). v je počet vrcholov grafu, m je počet hrán. Vrcholy su očíslované od 1 ... n. Ďalsích m riadkov bude obsahovať dve navzájom rôzne čísla vrcholov, ktoré popisujú obojsmernú hranu. Vstup je ukončený trojicou v=0, m=0, n=0, ktorá už nie je vstupnou sadou.

Vystup

Pre každú vstupnú sadu výstupom Vášho programu má byť jediný riadok v tvare "Pn-vertex are: ", za ktorým nasleduje zoznam Pn-vertex vrcholov v rastúcom poradí. Ak v grafe nie je žiaden Pn-vertex, výstupom má byť riadok "There is no Pn-vertex.". Detaily pozri z príkladu výstupu.

Príklad

Vstup:

9 10 8
1 4
4 2
4 8
4 7
5 2
5 8
8 9
9 7
5 3
6 3

5 8 5
1 2
1 3
2 3
2 5
3 4
2 4
3 5
4 5

4 5 5
1 2
1 4
1 3
4 3
4 2

0 0 0

Výstup:

P8-vertex are: 1 2 6 7 8
P5-vertex are: 1 2 3 4 5
There is no P5-vertex.

Príklad pridal Ján Katrenič.

© 2005-2015 Strom, PF UPJŠ