Cod sursa(job #640713)

Utilizator stefan.cStefan Cucea stefan.c Data 26 noiembrie 2011 13:06:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>
int n,viz[100005];
struct nod{int inf;
           nod *ad;}*v[100005];

void push(int a,int b)
{
	nod *tmp=new nod;
	tmp->inf=b;
	tmp->ad=v[a];
	v[a]=tmp;
}
		   
int par(int k)
{nod *curs=v[k];
 while(curs!=NULL){
	if(viz[curs->inf]==0){
	 viz[curs->inf]=1;
    par(curs->inf);
    }
	curs=curs->ad;
 }	
}
int main()
{int m,n,z=0,a,b,i;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);

for(i=1;i<=m;i++)
	{scanf("%d%d",&a,&b);
	 push(a,b);
	 push(b,a);
	}
for(i=1;i<=n;i++)
  if(viz[i]==0)
    {viz[i]=1;
	 par(i);
	 z++;
	}
printf("%d",z);	
return 0; 
}