Bacalaureat · Grafuri și arbori · clasa a 12-a
Componente conexe
Cerință
Afișează numărul de componente conexe ale grafului neorientat dat.
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, 0 ≤ m ≤ 100 000
- Sunt 20 de teste, fiecare valorează 5 puncte.
4 4 2 4 1 2 1 3 1 4
1
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Pornește o parcurgere din fiecare nod nevizitat; fiecare pornire înseamnă o componentă nouă. Rezultatul corect pentru acest exemplu este: 1.
7 7 2 4 5 7 4 5 1 7 3 6 1 3 3 5
1
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Pornește o parcurgere din fiecare nod nevizitat; fiecare pornire înseamnă o componentă nouă. Rezultatul corect pentru acest exemplu este: 1.
24 16 10 21 3 24 9 19 22 24 1 20 7 19 5 23 17 22 8 19 2 9 13 19 6 16 3 6 4 11 1 19 18 24
8
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Pornește o parcurgere din fiecare nod nevizitat; fiecare pornire înseamnă o componentă nouă. Rezultatul corect pentru acest exemplu este: 8.