Pagini recente » Cod sursa (job #2790250) | Cod sursa (job #2270201) | Cod sursa (job #1910244) | Cod sursa (job #657075) | Cod sursa (job #2816562)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
void explore(vector<vector<int>> adj_list, int x, vector<bool> &visited){
visited[x] = true;
vector<int>::iterator i;
for(i = adj_list[x].begin(); i < adj_list[x].end(); ++i){
if(!visited[*i]){
explore(adj_list, *i, visited);
}
}
}
int nr_conexe(vector<vector<int>> adj_list){
vector<bool> visited(adj_list.size(), false);
int cnt = 0;
for(unsigned i = 0; i < adj_list.size(); ++i){
if(!visited[i]){
cnt++;
explore(adj_list, i, visited);
}
}
return cnt;
}
int main(){
ifstream fin("dfs.in");
ofstream fout("dfs.out");
unsigned int N, M;
int x, y;
fin >> N >> M;
//cout << N << " " << M;
//cout << "\n";
vector<vector<int>> adj_list(N, vector<int>());
for(unsigned int i = 0; i < M; ++i){
fin >> x >> y;
adj_list[x - 1].push_back(y - 1);
adj_list[y - 1].push_back(x - 1);
}
//for(int i = 0; i < N; ++i){
//for(unsigned j = 0; j < adj_list[i].size(); ++j){
//cout << i + 1 << " " << adj_list[i][j] + 1 << " ";
//cout << "\n";
//}
//}
int nr = nr_conexe(adj_list);
fout << nr;
return 0;
}