Cod sursa(job #626748)
#include <stdio.h>
#include <vector>
using namespace std;
vector <int> lista[100010];
char vizitat[100010];
int marime[100010];
void dfs(int s){
int i;
for(i=0;i<marime[s];i++){
if(vizitat[lista[s][i]]==0){
vizitat[lista[s][i]]=1;
dfs(lista[s][i]);
}
}
}
int main(){
int n,m;
int i;
int a,b;
int conex=0;
FILE *fin=fopen("dfs.in","r");
fscanf(fin,"%d%d",&n,&m);
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&a,&b);
a--;b--;
lista[a].push_back(b);
marime[a]++;
lista[b].push_back(a);
marime[b]++;
}
fclose(fin);
//lista[i] contine toti vecinii nodului i
for(i=0;i<n;i++){
if(vizitat[i]==0){
//fac o parcurgere pronind de la nodul i
dfs(i);
conex++;
}
}
FILE *fout=fopen("dfs.out","w");
fprintf(fout,"%d\n",conex);
fclose(fout);
return 0;
}