Pagini recente » Cod sursa (job #280807) | Cod sursa (job #1242061) | Cod sursa (job #743105) | Cod sursa (job #2896294) | Cod sursa (job #1550220)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;
int n, m, a, b; //nr. de noduri/muchii
bool vizitat[nmax]; //vizitat[]
vector <int> v[nmax]; //listele de vecini
void dfs(int node) {
vizitat[node] = true;
for(auto vecin:v[node]) //C++11 (versiune mai noua)
if(!vizitat[vecin])
dfs(vecin);
}
int main() { //begin
ifstream f("dfs.in"); //assign f('dfs.in'); reset(f);
ofstream g("dfs.out"); //assign g('dfs.out'); rewrite(g);
f >> n >> m; //read(f, n, m);
//puteam si f>>n; f>>m;
for(int i=1; i<=m; i++) {
f >> a >> b;
v[a].push_back(b); //b e vecin al lui a
v[b].push_back(a); //a e vecin al lui b
}
int componente = 0;
for(int i=1; i<=n; i++)
if(!vizitat[i]) {
componente++;
dfs(i); //dfs(i) viziteaza toata componenta conexa a nodului i
}
g << componente << "\n"; //writeln(g, componente);
return 0;
}