Bacalaureat · Grafuri și arbori · clasa a 12-a
Graf complet
Cerință
Verifică dacă graful neorientat dat este complet (orice două noduri sunt unite). Afișează DA, sau NU urmat pe linia următoare de numărul de muchii lipsă.
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 și pe linia a doua numărul de muchii lipsă. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ n ≤ 60, fără muchii duble
- 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 complet are exact n·(n−1)/2 muchii. Rezultatul corect pentru acest exemplu este: DA.
4 3 1 4 2 3 3 4
NU 3
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Un graf complet are exact n·(n−1)/2 muchii. Rezultatul corect pentru acest exemplu este: NU 3.
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
DA
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Un graf complet are exact n·(n−1)/2 muchii. Rezultatul corect pentru acest exemplu este: DA.