Cod sursa(job #163949)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 23 martie 2008 12:49:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <string.h>
#include <stdio.h>
#define N 100000
#define M 200000
long n,m,c;
long muc[2*M+1][2];
long p[N],vf;
char viz[N];

void adauga(long a,long b)
{muc[++vf][0]=a;
 muc[vf][1]=p[b];
 p[b]=vf;

 muc[++vf][0]=b;
 muc[vf][1]=p[a];
 p[a]=vf;
}
void dfs(long v)
{for (long i=p[v];i;i=muc[i][1])
 {if(viz[muc[i][0]]==0)
  {viz[muc[i][0]]=1;
   dfs(muc[i][0]);
  }
 }
}
int main ()
{freopen("dfs.in","r",stdin);
 freopen("dfs.out","w",stdout);
 memset(viz,0,sizeof(viz));
 memset(p,0,sizeof(p));
 muc[0][0]=muc[0][1]=0;vf=0,c=0;
 scanf("%ld%ld",&n,&m);
 long a,b,i;
 for (i=1;i<=m;i++)
 {scanf("%ld%ld",&a,&b);
  adauga(a,b);
 }
 for (i=1;i<=n;i++)
 {if(viz[i]==0)
  {c++;
   dfs(i);
  }
 }
 printf("%ld",c);
 return 0;
}