Cod sursa(job #153420)

Utilizator megabyteBarsan Paul megabyte Data 10 martie 2008 15:24:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <vector>
#define INF "dfs.in"
#define OUF "dfs.out"
#define pb(arg) push_back(arg)
#define sz(arg) arg.size()
using namespace std;
const int NMAX=100002;
vector<int> a[NMAX];
char viz[NMAX]={0};

void dfs(int nd)
{
	int i,nb;
	viz[nd]=1;
	for(i=0;i<sz(a[nd]);++i)
	if(!viz[a[nd][i]])
	{
		nb=a[nd][i];
		dfs(nb);
	}
}

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	int i,aa,bb,n,m,cc=0;
	fscanf(in,"%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		fscanf(in,"%d%d",&aa,&bb);
		a[aa].pb(bb);
		a[bb].pb(aa);
	}
	
	for(i=1;i<=n;++i) if(!viz[i]) ++cc,dfs(i);
	
	fprintf(out,"%d\n",cc);
	fclose(in);fclose(out);
	return 0;
}