Cod sursa(job #152919)

Utilizator maria_pparcalabescu maria daniela maria_p Data 9 martie 2008 22:02:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<cstdio>

const long MAX=100100;

long n,m,nr,i,x,y;
bool used[MAX];
struct point{
	long x;
	point *leg;
}*p,*lista[MAX];

void dfs(long k){
	point *q;
	used[k]=1;
	for(q=lista[k];q!=0;q=q->leg)
		if(used[q->x]==0)
			dfs(q->x);
}

int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=0;i<m;i++){
		scanf("%ld%ld",&x,&y);
		p=new point;
		p->x=y;p->leg=lista[x];lista[x]=p;
		p=new point;
		p->x=x;p->leg=lista[y];lista[y]=p;
	}
	nr=0;
	for(i=1;i<=n;i++)
		if(used[i]==0){
			nr++;
			dfs(i);
		}
	printf("%ld\n",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}