Pagini recente » Cod sursa (job #2200684) | Cod sursa (job #2629491) | Cod sursa (job #1326834) | Cod sursa (job #1202494) | Cod sursa (job #3167917)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
const int N_MAX = 100001;
vector<int> vecini[N_MAX];
int n, m, nrConexe;
bool viz[N_MAX];
void read(){
f >> n >> m;
for(int i = 0, n1, n2; i < m; ++i){
f >> n1 >> n2;
vecini[n1].push_back(n2);
vecini[n2].push_back(n1); /// fiind neorientat, muchiile merg in doua sensuri
}
}
void DFS(int nod){ /// = Depth first search
viz[nod] = true;
for(auto i : vecini[nod]){
if( !viz[i])
DFS(i);
}
}
int main()
{
read();
for(int i = 1; i <= n; ++i){
if( !viz[i]){
nrConexe++;
DFS(i);
}
}
g << nrConexe;
return 0;
}