Pagini recente » Cod sursa (job #2966245) | Cod sursa (job #2127581) | Cod sursa (job #601391) | Cod sursa (job #501750) | Cod sursa (job #870220)
Cod sursa(job #870220)
#include<stdio.h>
int n,m,start[100002], t[2][400002];
int s,x,y,i,j,z;
int stiva[100002];
int viz[100002],k,nr;
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++;
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--;
}
}
}
}
printf("%d ",nr);
fclose(stdin);
fclose(stdout);
return 0;
}