Cod sursa(job #638635)

Utilizator Robert29FMI Tilica Robert Robert29 Data 21 noiembrie 2011 10:21:54
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>
FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");

int n,m,x,y,sol;
char a[100001];

struct point{
	int inf;
	point *adr;
} *p,*q,*L[100001];



void dfs(int nod){
	a[nod]=1;
	q=L[nod];
	while(q!=NULL){
		if(!a[q->inf])
			dfs(q->inf);
		q=q->adr;
	}
	
	return;
}
int main(){
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		L[i]= NULL;
	
	
	for(int i=1;i<=m;++i){
		fscanf(f,"%d%d",&x,&y);
		q=new point;
		q->inf=y;
		q->adr=L[x];
		L[x]=q;
		
		
		q=new point;
		q->inf=x;
		q->adr=L[y];
		L[y]=q;
		
	}
	
	for(int i=1;i<=n;++i){
		if(!a[i]){
			dfs(i);
			++sol;
		}
		
	}
	fprintf(g,"%d",sol);
	
	fclose(g);
	fclose(f);
	return 0;
}