Cod sursa(job #704981)

Utilizator remus_maziluRemus Mazilu remus_mazilu Data 2 martie 2012 22:41:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include<cstdio>
#include<vector>
using namespace std;

vector <int> v[100001];

int viz[100001];
int k,x,y,n,m,i;
void dfs(int x)
{
	viz[x]=1;
	for(int i=0;i<v[x].size();i++)
	{
		if(!viz[v[x][i]])
			dfs(v[x][i]);
	}
}

main()
{
	FILE * in=fopen("dfs.in","r");
	FILE * out=fopen("dfs.out","w");
	
	fscanf(in,"%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(in,"%d%d",&x,&y);
		v[x].push_back(y);v[y].push_back(x);
	}
	for(i=1;i<=n;i++)
	{
		if(!viz[i])
			k++,dfs(i);
	}
	fprintf(out,"%d\n",k);
}