Pagini recente » Cod sursa (job #683998) | Cod sursa (job #1486186) | Cod sursa (job #2202575) | Cod sursa (job #2599979) | Cod sursa (job #285035)
Cod sursa(job #285035)
#include<stdio.h>
int n,m,stiva[100001],viz[100001],ncc;
struct nod{
int info;
nod *adr;
};
struct lista{
nod *vf,*sf;
};
lista v[100001];
nod *uv[100001];
void addend(lista &l,int x){
nod *n=new nod;
n->info=x;
n->adr=NULL;
if(!l.vf) l.vf=n;
else l.sf->adr=n;
l.sf=n;
}
void dfs(int start){
int k,up,x;
k=1;
stiva[k]=start;
viz[start]=1;
uv[k]=v[start].vf;
while(k){
up=0;
while(!up&&uv[k]){
x=uv[k]->info;
if(!viz[x]){
up=1;
}
uv[k]=uv[k]->adr;
}
if(up){
k++;
stiva[k]=x;
viz[x]=1;
uv[k]=v[x].vf;
}
else k--;
}
}
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y;
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
addend(v[x],y);
addend(v[y],x);
}
for(i=1;i<=n;i++)
if(!viz[i]){
ncc++;
dfs(i);
}
printf("%d",ncc);
return 0;
}