Problema NP-completa oare?

[•nparfene2004]

Salut,

As vrea sa ma ajutati cu un raspuns la problema urmatoare: Se da un graf conex si un nod in acest graf. Sa se verifice daca acest nod face parte sau nu dintr-un ciclu.

Este aceasta o problema NP-completa? Sa stiu cum abordez rezolvarea.
Multumesc!

[•pauldb]

Un nod intr-un graf nu face parte dintr-un ciclu daca si numai daca toate muchiile incidente sunt critice. Problema determinarii muchiilor critice are complexitate O(N+M).

[•devilkind]

De fapt nu cred ca trebuie sa calculezi muchiile critice. Cred ca daca faci un simplu DF din nodul respectiv, trebuie sa vezi daca exista vreo muchie de intoarcere incidenta cu nodul initial. Cred ca sunt echivalente solutia mea cu a lu paul, doar ca eu verific intr-o modalitate ceva mai simpla.

[•wefgef]

Tibi are dreptate, insa daca vrei sa afli pentru toate nodurile din graf daca aparatin vreunui ciclu trebuie sa determini muchiile critice.