Cod sursa(job #516927)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 27 decembrie 2010 09:43:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100001
typedef struct nod
{long info;
struct nod *leg;}Nod,*list_ad;
typedef struct
{long grin;
list_ad lad;}head;
typedef head graf[N];
graf g;

typedef struct stack
{long st[N],sp;};
long n,m,c[N],i,j,k,t;

void add(list_ad &l,long x)
{Nod *px=new Nod;
px->info=x;
px->leg=l;
l=px;}

long del(list_ad &l)
{long x=l->info;
Nod *t=l->leg;
free(l);
l=t;
return x;}

void push(stack &s,long x)
{s.st[++s.sp]=x;}

long pop(stack &s)
{return s.st[s.sp--];}

int main()
{freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
stack s;
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
       {c[i]=0;
       g[i].grin=0;
       g[i].lad=NULL;}
for(k=1;k<=m;k++)
       {scanf("%ld%ld",&i,&j);
       g[i].grin++;
       g[j].grin++;
       add(g[i].lad,j);
       add(g[j].lad,i);}
t=0;
for(i=1;i<=n;i++)
if(c[i]==0)
       {t++;
       s.sp=0;
       push(s,i);
       while(s.sp!=0)
               {k=pop(s);
               c[k]=1;
               while(g[k].grin!=0)
                     {j=del(g[k].lad);
                     g[k].grin--;
                     if(c[j]==0)
                           push(s,j);}}}
printf("%ld\n",t);
fclose(stdin);
fclose(stdout);
return 0;}