Bacalaureat · Grafuri și arbori · clasa a 12-a
Muchii pentru conexitate
Cerință
Află numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex.
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
Un singur număr. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ n ≤ 100 000
- Sunt 20 de teste, fiecare valorează 5 puncte.
4 1 3 4
2
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Cu k componente sunt necesare exact k − 1 muchii. Rezultatul corect pentru acest exemplu este: 2.
7 6 2 4 3 4 4 6 2 6 3 6 2 5
2
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Cu k componente sunt necesare exact k − 1 muchii. Rezultatul corect pentru acest exemplu este: 2.
24 21 12 13 5 7 22 23 12 22 8 15 8 21 6 14 18 19 12 24 3 21 9 19 1 11 8 20 7 12 5 11 5 8 5 23 10 13 1 7 9 18 19 22
5
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Cu k componente sunt necesare exact k − 1 muchii. Rezultatul corect pentru acest exemplu este: 5.