Pagini recente » Cod sursa (job #1472578) | Cod sursa (job #277416) | Cod sursa (job #2328103) | Cod sursa (job #447823) | Cod sursa (job #3351448)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int numar_noduri, numar_arce;
cin >> numar_noduri >> numar_arce;
// 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;
queue<int> neighbours;
for (int starting_node = 1; starting_node <= numar_noduri; ++starting_node) {
if (vizited[starting_node]) {
continue;
}
neighbours.push(starting_node);
++conex_components;
while (!neighbours.empty()) {
int current_node = neighbours.front();
neighbours.pop();
for (int neighbour : graf[current_node]) {
if (!vizited[neighbour]) {
neighbours.push(neighbour);
vizited[neighbour] = true;
}
}
}
}
cout << conex_components << "\n";
return 0;
}