Cod sursa(job #263608)

Utilizator adrian69adrian horia adrian69 Data 20 februarie 2009 18:06:19
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 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()
{nod *p;
 while(cap<=coada)
 {
  p=a[b[cap]];
  while(p)
  { 
	if(c[p->no]==0)
    {c[p->no]=1;
    b[coada++]=p->no;
    }
	p=p->urm;
  }	  
  cap++;
 } 
}
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)
   {c[i]=1;
    b[++coada]=i;
	dfs();
    contor++;
   } 
	printf("%d ",contor);  
 printf("\n");
 return 0;
}