Pagini recente » Cod sursa (job #399142) | Cod sursa (job #505271) | Cod sursa (job #809669) | Cod sursa (job #1798961) | Cod sursa (job #548474)
Cod sursa(job #548474)
#include<fstream.h>
#define NM 100001
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod{
int nr;
nod *next;
};
int m,n,viz[NM],cc;
nod *l[NM], *urm[NM];
void add(nod *&l ,int x){
nod*m=new(nod);
m->nr=x;
m->next=l;
l=m;
}
void build(){
int x,y,i;
fin>>n>>m;
for(i=0;i<m;i++){
fin>>x>>y;
add(l[x],y);
add(l[y],x);
}
}
void df(int x){
int y;
nod*uc=urm[x];
while(uc){
viz[x]=cc;
y=uc->nr;
uc=uc->next;
if(!viz[y])
df(y);
urm[x]=uc;
}
}
int main(){
int i;
build();
for(i=1;i<=n;i++)
urm[i]=l[i];
for(i=1;i<=n;i++)
if(!viz[i])
{ cc++;
df(i);
}
fout<<cc;
return 0;
}