Cod sursa(job #515401)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 21 decembrie 2010 13:33:31
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#define N 100001
#define M 200001
typedef struct stack
{long st[N],sp;};
long n,m,a1[M],a2[M],c[N],k,i,t,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(k=1;k<=m;k++)
       scanf("%ld%ld",&a1[k],&a2[k]);
for(i=1;i<=n;i++)
       c[i]=0;
t=0;
for(i=1;i<=n;i++)
if(c[i]==0)
       {t++;
       s.sp=0;
       push(s,i);
       while(s.sp!=0)
               {x=pop(s);
               c[x]=1;
               for(k=1;k<=m;k++)
               if(a1[k]==x&&c[a2[k]]==0)
                       push(s,a2[k]);
               else
                       if(a2[k]==x&&c[a1[k]]==0)
                                push(s,a1[k]);}}
printf("%ld\n",t);
fclose(stdin);
fclose(stdout);
return 0;}