Graf acíclic? P59061
Donat un graf no dirigit, digueu si se’n pot esborrar exactament una aresta de manera que quedi un graf acíclic.
Entrada
L’entrada consisteix en diversos casos. Cada cas comença amb n i m, el nombre de vèrtexs i arestes del graf, respectivament. Segueixen m parells x y, indicant una aresta entre x i y, amb x ≠ y. Suposeu que n i m es troben entre 1 i 105, que els vèrtexs es numeren començant en 0, i que no hi ha més d’una aresta entre dos vèrtexs.
Sortida
Per a cada cas, escriviu “yes” si es pot esborrar una aresta de manera que el resultat sigui un graf acíclic, i “no” altrament.
Observació
La solució esperada té cost Θ(n + m).
Public test cases
Input
2 1 1 0 5 4 0 1 1 2 2 0 3 4 6 6 0 1 1 2 0 2 3 4 4 5 5 3
Output
yes yes no
Information
- Author
- Izan Beltran
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++