Pagini recente » Cod sursa (job #937562) | Cod sursa (job #1024170) | Cod sursa (job #1057793) | Cod sursa (job #2630241) | Cod sursa (job #159191)
Cod sursa(job #159191)
#include <stdio.h>
struct nod{
nod *urm;
long nd;
}*p[100010],*aux;
long n,m,i,x,y,marc[100010],nmarc,n_con;
void dfs(long nxd)
{ nod *aux;
marc[nxd]=1;
for(aux=p[nxd];aux!=NULL;aux=aux->urm)
if (!marc[aux->nd]) dfs(aux->nd);
}
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%ld%ld", &n,&m);
for(i=0;i<m;i++){
scanf("%ld%ld",&x,&y);
aux=new nod;
aux->urm=p[x];
aux->nd=y;
p[x]=aux;
aux=new nod;
aux->urm=p[y];
aux->nd=x;
p[y]=aux;
}
long gasit=1,poz_aux=1;
while(gasit){
gasit=0;
for(i=poz_aux;i<=n;i++) if (marc[i]==0) {gasit=1;poz_aux=i;break;}
if (gasit){dfs(i);n_con++;}
}
printf("%ld",n_con);
return 0;
}