Pagini recente » Cod sursa (job #2727256) | Cod sursa (job #649803) | Cod sursa (job #2728721) | Cod sursa (job #2686332) | Cod sursa (job #870223)
Cod sursa(job #870223)
#include<stdio.h>
int n,m,start[100002], t[2][400002];
int s,x,y,i,j,z;
int stiva[100002];
int viz[100002],nr;
void dfs(int vf){
int k,x,y,j,z;
stiva[1]=s;
k=1;
viz[s]=1;
while(k>0){
x=stiva[k];
z=0;
for(j=start[x];j!=0;j=t[1][j]){
y=t[0][j];
if(viz[y]==0){
z=1;
j=0;
}
}
if(z!=0){
k++;
stiva[k]=y;
viz[y]=1;
}
else{
k--;
}
}
}
int main(){
freopen("dfs.in","rt",stdin);
freopen("dfs.out","wt",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++){
start[i]=0;
viz[i]=0;
}
j=0;
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
j++;
t[0][j]=y;
t[1][j]=start[x];
start[x]=j;
j++;
t[0][j]=x;
t[1][j]=start[y];
start[y]=j;
}
nr=0;
for (s=1;s<=n;s++){
if(viz[s]==0){
nr++;
dfs(s);
}
}
printf("%d ",nr);
fclose(stdin);
fclose(stdout);
return 0;
}