Cod sursa(job #160143)

Utilizator pandaemonAndrei Popescu pandaemon Data 14 martie 2008 19:31:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>
#define LMAX 100001

long n,m,i,contor; char viz[LMAX];

struct nod {long val; nod *next;} *v[LMAX];

void adauga(nod *&before,long aux)
{ nod *p=new nod;
  p->next=before;
  p->val=aux;
  before=p; }

long dfs(long nodc)
{nod *p=v[nodc];

 for(;p!=NULL;p=p->next)
  if(viz[p->val]==0)
     {viz[p->val]=1; dfs(p->val);} }


void citire()
{scanf("%ld %ld",&n,&m); long aux1,aux2;

 for(i=1;i<=m;i++)
 { scanf("%ld %ld",&aux1,&aux2);
   adauga(v[aux1],aux2);
   adauga(v[aux2],aux1); }          }


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

  citire();

  for(i=1;i<=n;i++)
  if(viz[i]==0) { contor++; viz[i]=1; dfs(i); }


 printf("%ld\n",contor);


 return 0;}