Cod sursa(job #233055)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 16 decembrie 2008 19:49:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<stdio.h>
typedef struct pct{long x;pct *a;} *pc;
pc p[100005],pp;
long n,m,i,x,y,v[100005],nr;
void dfs(long a)
{pc p1;
 v[a]=1;
 for(p1=p[a];p1!=NULL;p1=p1->a)
    if(!v[p1->x])
      dfs(p1->x);
}
int main()
{
 freopen("dfs.in","r",stdin);
 freopen("dfs.out","w",stdout);
 scanf("%ld%ld",&n,&m);
 for(i=1;i<=m;++i)
    {scanf("%ld%ld",&x,&y);
     pp=new pct;
     pp->x=y;
     pp->a=p[x];
     p[x]=pp;
     pp=new pct;
     pp->x=x;
     pp->a=p[y];
     p[y]=pp;}
for(i=1;i<=n;++i)
    if(!v[i])
      {++nr;
       dfs(i);}
 printf("%ld\n",nr);
 return 0;
}