Cod sursa(job #709409)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 8 martie 2012 08:17:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>
#define val 100010
int i , n , m , x , y ,nr , Fr[val];
struct nod{
	int nr;
	nod *adr;
}*p,*L[val];

FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");

void dfs(int e){
	nod *c;
	c=L[e];
	while(c!=NULL){
		if(Fr[c->nr]==0){
			Fr[c->nr]=1;
			dfs(c->nr);
		}
		c=c->adr;
	}
}

int main(){
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d",&x,&y);
		p=new nod;
		p->nr=y;
		p->adr=L[x];
		L[x]=p;
		p=new nod;
		p->nr=x;
		p->adr=L[y];
		L[y]=p;
	}
	
	for(i=1;i<=n;i++){
		if(Fr[i]==0){
			nr++;Fr[i]=1;
			dfs(i);
		}
	}
	fprintf(g,"%d",nr);
	return 0;
}