Ciclu in graf

[•nparfene2004]

V-as ruga sa-mi dati si mie cateva indicatii la urmatoarea problema:

Se da un graf neorientat si un nod x din acest graf. Sa se verifice daca exista un ciclu care trece prin x si in caz ca exista sa se afiseze.

Ma intereseaza o solutie de complexitate polinomiala. Multumesc.

[•AlexandruValeanu]

Faci o parcurgere (DFS/BFS) din nodul X si daca la un moment dat ajungi intr-un nod Y si muchia (Y,X) exista, ai un ciclu si printezi drumul de la X la Y. Trebui sa ai grija si prin ce muchie ajungi in Y.