Pagini recente » Cod sursa (job #311910) | Cod sursa (job #1318213) | Cod sursa (job #2117794) | Cod sursa (job #387847) | Cod sursa (job #3351462)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void DFS(vector<vector<int>>& graf, vector<bool>& vizited, int nod) {
vizited[nod] = true;
for (int neighbour : graf[nod]) {
if (!vizited[neighbour]) {
DFS(graf, vizited, neighbour);
}
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int numar_noduri, numar_arce;
if (!(cin >> numar_noduri >> numar_arce)) {
return 1;
}
// citim arcele si construim matricea de legatura
vector<vector<int>> graf(numar_noduri + 2);
while (numar_arce--) {
int baza, target;
cin >> baza >> target;
graf[baza].push_back(target);
graf[target].push_back(baza);
}
vector<bool> vizited(numar_noduri + 2, false);
int conex_components = 0;
for (int starting_node = 1; starting_node <= numar_noduri; ++starting_node) {
if (!vizited[starting_node]) {
DFS(graf, vizited, starting_node);
++conex_components;
}
}
cout << conex_components << "\n";
return 0;
}