Cod sursa(job #886473)

Utilizator sandruSandru Petru-Ionut sandru Data 22 februarie 2013 21:22:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>
#include<vector>
using namespace std;
vector<long> vec[100001];
long m,n,raspuns;
long v[100001];
void dfs(long nod)
{
	v[nod]=1;
	for(long i=0;i<vec[nod].size();i++)
		if(v[vec[nod][i]]==0)
			dfs(vec[nod][i]);
}
int main()
{
	FILE *f;
	FILE *g;
	f=fopen("dfs.in","rt");
	g=fopen("dfs.out", "wt");
	fscanf(f,"%d %d", &n, &m);
	for(long i=1;i<=m;i++)
	{long x,y;
	 fscanf(f,"%d %d", &x, &y);
	 vec[x].push_back(y);
	 vec[y].push_back(x);
	} 
	for(long i=1;i<=n;i++)
		if(v[i]==0)
		{
			dfs(i);
			raspuns++;
		}
	fprintf(g,"%d", raspuns);
	fclose(f);
	fclose(g);
	return 0;
}