Cod sursa(job #639888)

Utilizator KoniacDocea Andrei Koniac Data 24 noiembrie 2011 10:54:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 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;
	struct point *adr;
} *p,*q,*L[100001];


void dfs(int nod){
	a[nod]=1;
	for(point *q=L[nod];q!=NULL;q=q->adr){
		if(!a[q->inf])
			dfs(q->inf);
	}
	
}


int main(){
	fscanf(f,"%d%d",&n,&m);

	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;
}