Bacalaureat · Grafuri și arbori · clasa a 12-a
Are graful un ciclu?
Cerință
Afișează DA dacă graful neorientat conține cel puțin un ciclu, altfel NU.
Problemă originală de antrenament, nu este subiect oficial.
Date de intrare
Pe prima linie se află n și m (noduri, muchii). Pe următoarele m linii câte o muchie x y.
Date de ieșire
DA sau NU. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ n ≤ 50 000
- Sunt 20 de teste, fiecare valorează 5 puncte.
3 3 1 2 1 3 2 3
DA
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Un graf fără cicluri (pădure) cu k componente are exact n − k muchii. Rezultatul corect pentru acest exemplu este: DA.
5 4 5 3 3 1 4 2 2 1
NU
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Un graf fără cicluri (pădure) cu k componente are exact n − k muchii. Rezultatul corect pentru acest exemplu este: NU.
17 16 8 3 2 4 11 15 7 16 1 17 12 2 9 4 10 2 13 2 14 16 5 16 3 17 15 14 17 7 16 4 6 9
NU
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Un graf fără cicluri (pădure) cu k componente are exact n − k muchii. Rezultatul corect pentru acest exemplu este: NU.