Pagini recente » Cod sursa (job #678093) | Cod sursa (job #2097406) | Cod sursa (job #1896427) | Cod sursa (job #1992899) | Cod sursa (job #2590138)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
vector <vector<int>> neighbours (100001);
bitset <100001> visited;
ifstream fin;
ofstream fout;
int nodes, edges, i, j, n, k, aux, components;
void DFS_search(int where_to_start){
visited[where_to_start] = true;
for (vector<int>::iterator it = neighbours[where_to_start].begin(); it!=neighbours[where_to_start].end(); it++)
if (!visited[*it]) DFS_search(*it);
}
int main (void){
fin.open("dfs.in");
fin>>nodes>>edges;
for (i=1; i<=edges; i++){
fin>>j>>k;
neighbours[j].push_back(k);
neighbours[k].push_back(j);
}
fin.close();
for (i=1; i<=nodes; i++)
if (!visited[i]) {
DFS_search(i);
components++;
}
fout.open("dfs.out");
fout<<components<<"\n";
fout.close();
return 0;
}