Pagini recente » Cod sursa (job #2697135) | Cod sursa (job #2871371) | Cod sursa (job #1426101) | Cod sursa (job #2836214) | Cod sursa (job #3250937)
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void dfs(int start, const vector<vector<int>>& addiacence, unordered_set<int>& visited){
queue<int> to_visit;
visited.insert(start);
to_visit.push(start);
while (!to_visit.empty()){
int curr = to_visit.front();
for (const auto& neighbour : addiacence[curr])
if (visited.find(neighbour) == visited.end()){
to_visit.push(neighbour);
visited.insert(neighbour);
}
to_visit.pop();
}
}
int main(){
int nr_nodes, nr_links;
fin >> nr_nodes >> nr_links;
vector<vector<int>> addiacence(nr_nodes + 1);
for (int i = 0; i < nr_links; ++i){
int node1, node2;
fin >> node1 >> node2;
addiacence[node1].push_back(node2);
addiacence[node2].push_back(node1);
}
unordered_set<int> visited;
int nr_components = 0;
for (int i = 1; i <= nr_nodes; ++i)
if (visited.find(i) == visited.end()){
nr_components ++;
dfs(i, addiacence, visited);
}
fout << nr_components;
}