Cod sursa(job #562501)

Utilizator Robert29FMI Tilica Robert Robert29 Data 23 martie 2011 10:32:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include<stdio.h>
#include<vector>
using namespace std;
FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");
vector <int> v[100001];
int n,m,x,y,i,a[100001];

void dfs(int nod){
	a[nod]=1;

	for(int j=0;j<v[nod].size();++j)
		if(a[v[nod][j]]==0)
			dfs(v[nod][j]);
}
int main(){
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;++i){
		fscanf(f,"%d%d",&x,&y);
		v[x].push_back (y); 
		v[y].push_back (x); 
	}
	x=0;
	
	for(i=1;i<=n;++i)
		if(!a[i]){
			dfs(i);
			++x;
		}
	fprintf(g,"%d",x);
	fclose(g);
	fclose(f);
	return 0;
}