Cod sursa(job #276583)

Utilizator vladbBogolin Vlad vladb Data 11 martie 2009 11:21:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>

struct nod { int v;
	     nod *next;
	   } *v[100010];
long n,m,pus[100010],cont;

void citire()
{   long i,x,y;
    nod *nou;
    freopen("dfs.in","r",stdin);
    scanf("%ld%ld",&n,&m);
    for(i=1;i<=m;i++)
    {	scanf("%ld%ld",&x,&y);
	    nou=new nod;
	    nou->v=y;
	    nou->next=v[x];
	    v[x]=nou;
	    nou=new nod;
	    nou->v=x;
	    nou->next=v[y];
	    v[y]=nou;
    }
}

void df(long k)
{	nod *p;
	pus[k]=1;
	p=v[k];
	while(p!=NULL)
	{	if(pus[p->v]==0) df(p->v);
		p=p->next;
	}
}	

int main()
{   freopen("dfs.out","w",stdout);
    long i;
    nod *p;
    citire();
    for(i=1;i<=n;i++)
    	if(pus[i]==0){ df(i);
					   cont++;
					 }
    printf("%ld",cont);			   
    return 0;
}