Cod sursa(job #283456)
# include <stdio.h>
int n,a[1010][1010],vizitat[1010],st[1010],vf,k,m,nr,nr1;
void citire(){
int i,j,k,m;
scanf("%d%d",&n,&m);
for(k=1;k<=m;k++){
scanf("%d%d",&i,&j);
a[i][j]=a[j][i]=1;
}
}
int cauta(){
for(int i=1;i<=n;i++)
if(vizitat[i]==0)
return i;
return 0;
}
void init(int k){
vf=1;
st[vf]=k;
vizitat[k]=1;
}
int este_vida(){
return vf==0;
}
void adaug(int i){
vf++;
st[vf]=i;
vizitat[i]=1;
}
void elimin(){
vf--;
}
void prelucrare(){
int i=1,k=st[vf];
while(i<=n && (a[i][k]==0 || (a[i][k]==1 && vizitat[i]==1))) i++;
if(i==n+1)
elimin();
else {nr++;
adaug(i);
}
}
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
citire();
k=cauta();
while(k){
m++;
init(k);
while(!este_vida()) prelucrare();
k=cauta();
}
printf("%d",m);
return 0;
}