Pagini recente » Cod sursa (job #3041678) | Cod sursa (job #1588630) | Cod sursa (job #3142048) | Cod sursa (job #2923901) | Cod sursa (job #1704178)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> adj_list;
vector<bool> viz;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
int N, M;
void read(){
f >> N >> M;
adj_list.resize(N + 1);
viz.resize(N + 1);
for(int x, y, i = 1; i <= N; i++) {
f >> x >> y;
adj_list[x].push_back(y);
adj_list[y].push_back(x);
}
}
int dfs(int start_node){
viz[start_node] = true;
vector<int>::iterator it;
for (it = adj_list[start_node].begin(); it != adj_list[start_node].end(); ++it) {
if(!viz[*it]){
dfs(*it);
}
}
}
int main() {
int number_of_components = 0;
read();
for (int i = 1; i <= N; ++i) {
if(!viz[i]){
dfs(i);
number_of_components++;
}
}
g << number_of_components << '\n';
g.close();
return 0;
}