Bacalaureat · Grafuri și arbori · clasa a 12-a
Este arbore?
Cerință
Afișează DA dacă graful neorientat dat este arbore (conex și fără cicluri), 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 1 1 3
NU
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Arbore = conex și cu exact n − 1 muchii. Rezultatul corect pentru acest exemplu este: NU.
5 4 5 1 1 2 3 1 4 1
DA
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Arbore = conex și cu exact n − 1 muchii. Rezultatul corect pentru acest exemplu este: DA.
17 16 12 10 17 8 14 17 11 4 9 7 6 14 2 14 3 17 4 1 1 10 15 1 10 9 13 3 5 12 7 8 16 6
DA
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Arbore = conex și cu exact n − 1 muchii. Rezultatul corect pentru acest exemplu este: DA.