Cod sursa(job #263321)

Utilizator ditiBilescu Adrian diti Data 20 februarie 2009 10:16:19
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#define MAX 110000
long vizitat[MAX],v,parc[MAX],rez[MAX],k;

 struct nod
 {
    int info;
    nod *adress; 
 };
nod *q[MAX];


void adauga(int a,int k)
{
 	nod *element=new nod;
 	element->info=k;
	if (q[a]==NULL)
	 {
		 q[a]=element;
			element->adress=NULL;
		}
	else
		{
			element->adress=q[a];
			q[a]=element;
		}
}

void dfs(int a)
{
 nod *parc=q[a];

 while(parc!=NULL)
  {
    if(!vizitat[parc->info])
     {
       ++vizitat[parc->info];
       dfs(parc->info);
     }
       parc=parc->adress;
   }
}

int main()
{
 long i,s,x,y,m,n;
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);
    adauga(x,y);
   }
 s=0;
 for(i=1;i<=n;++i)
  {
    if(!vizitat[i])
    {dfs(i);
     ++s;  
     }
  }
 printf("%ld",s);
 
return 0;
}