Cod sursa(job #1274880)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 24 noiembrie 2014 15:15:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <stdio.h>
#include <vector>

using namespace std;
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
vector<int>a[100005];
vector<int>::iterator it;
int use[100005],i,n,x,y,m,nr;

void df(int k){
    int i;
//for(it=a[k].begin();it!=a[k].end();it++)
for(i=0;i<a[k].size();i++)
if (use[a[k][i]]==0){use[a[k][i]]=1;df(a[k][i]);}
}


int main()
{
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(f,"%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
for(i=1;i<=n;i++)
if (use[i]==0){nr++;use[i]=1;df(i);}

fprintf(g,"%d",nr);
fclose(g);
return 0;
}