Pagini recente » Cod sursa (job #835076) | Cod sursa (job #9967) | Cod sursa (job #2034574) | Cod sursa (job #2322466) | Cod sursa (job #158155)
Cod sursa(job #158155)
//Componente conexe
#include <cstdio>
typedef struct nod{int info;
nod *urm;}NOD;
NOD *prim[100002],*ult[100002];
int n,m,viz[100002],nr=0;
void add(int where,int what){
NOD *p;
p=new NOD;
p->info=what;
p->urm=NULL;
if (prim[where]==NULL) prim[where]=ult[where]=p;
else {ult[where]->urm=p;
ult[where]=p;}
}
void citeste(){
int i,j,k;
freopen("dfs.in","r",stdin);
scanf("%d %d",&n,&m);
for (i=1;i<=n;i++) {prim[i]=NULL;
viz[i]=0;}
for (k=1;k<=m;k++) {scanf("%d %d",&i,&j);
add(i,j);
add(j,i);}
}
void df(int vf){
NOD *p;
viz[vf]=1;
p=prim[vf];
while (p!=NULL) {if (viz[p->info]==0) df(p->info);
p=p->urm;}
}
void solve(){
int i;
for (i=1;i<=n;i++) if (!viz[i]) {nr++;
df(i);}
freopen("dfs.out","w",stdout);
printf("%d",nr);
fclose(stdout);
}
int main(){
citeste();
solve();
return 0;
}