Cod sursa(job #308038)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 25 aprilie 2009 21:37:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
# include <stdio.h>
int i,k,v[100001],x,y,q,n,m;
struct nod
{
int info;
nod *urm;
}*a[100001],*p;

void dfs (int x)
{
nod *z;
v[x]=1;
z=a[x];
while (z)
{
if (v[z->info]==0)
dfs (z->info);
z=z->urm;
}
}




int main ()
{
freopen ("dfs.in","r",stdin);
freopen ("dfs.out","w",stdout);

scanf ("%i%i",&n,&m);
for (i=1;i<=m;i++)
{
scanf ("%i%i",&x,&y);
p=new nod;
p->info=x;
p->urm=a[y];
a[y]=p;
p=new nod;
p->info=y;
p->urm=a[x];
a[x]=p;
}
for (k=1;k<=n;k++)
if (v[k]==0)
{
dfs (k);
q++;
}
printf ("%i",q);
return 0;
}