Cod sursa(job #499689)

Utilizator DanutzRusu Dan Andrei Danutz Data 10 noiembrie 2010 17:42:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
struct nod{
	long inf;
	nod *urm;
};
nod *L[100005];
int uz[100005];
long m,n;
FILE *f,*g;
void add(nod *&vf,long k){
	nod *q;
	q=new nod;
	q->inf=k;
	q->urm=vf;
	vf=q;
}

void cit(){
	long i,j,k;
	f=fopen("dfs.in","r");
	fscanf(f,"%ld %ld",&n,&m);
	for (k=1;k<=m;k++)
	{
		fscanf(f,"%ld %ld",&i,&j);
		add(L[i],j);
		add(L[j],i);
	}
	fclose(f);
}

void df(long k){
	uz[k]=1;
	nod *q;
	for (q=L[k];q;q=q->urm)
		if (!uz[q->inf])
			df(q->inf);
}

void solve(){
	long i,nr=0;
    for (i=1;i<=n;i++)
		if (!uz[i])
		{ nr++; df(i); }
	g=fopen("dfs.out","w");
	fprintf(g,"%ld\n",nr);
	fclose(g);
}

int main(){
	cit();
	solve();
	return 0;
}