Cod sursa(job #272640)

Utilizator 630r63Ilinca George Mihai 630r63 Data 7 martie 2009 16:14:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>

struct nod
{
 int no;
 nod *urm;
};
nod *a[100005];
int n,m;
int b[100005],c[100005];
int cap,coada;
void add(int x,int y)
{
 nod *p=new nod;
 p->no=y;
 p->urm=a[x];
 a[x]=p;
}
void dfs(int x)
{nod *p;
 c[x]=1;
 for(p=a[x];p!=NULL;p=p->urm) 
	 if(!c[p->no])
        dfs(p->no);		 
}
int main()
{int v,x,y;
 freopen("dfs.in","r",stdin);
 freopen("dfs.out","w",stdout);
 scanf("%d %d",&n,&m); 
 int i;
 for(i=1;i<=m;i++)
 {scanf("%d %d",&x,&y);
  add(x,y);
  add(y,x);
 } 
 
// b[cap]=1;
// coada++;
 
 int contor=0;
 for(i=1;i<=n;i++)
   if(c[i]==0)
   {
    contor++;
	dfs(i);
    
   } 
	printf("%d ",contor);  
 printf("\n");
 return 0;
}