Pagini recente » Cod sursa (job #270003) | Profil cristiz0ne | Cod sursa (job #1881364) | Cod sursa (job #366808) | Cod sursa (job #161497)
Cod sursa(job #161497)
#include <stdio.h>
#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
int ap[100000],n,m,componente;
typedef struct nod {
int x;
nod *a;
} *pNod;
pNod g[100000];
void dfs(int nod){
pNod p;
ap[nod]=1;
for(p = g[nod] ; p != NULL ; p = p -> a )
if( ! ap [ p -> x ] ) dfs ( p -> x );
}
void adauga(pNod &z, int v){
pNod q;
q=new nod;
q -> x = v;
q -> a = z ;
z = q;
}
void date(){int a,b;
FILE *fin=fopen(INPUT,"rt");
fscanf(fin,"%d %d",&n,&m);
for(int i=1;i<=m;i++){
fscanf(fin,"%d %d",&a,&b);
adauga(g[a],b);
adauga(g[b],a);
}
}
int main(){
FILE *fout=fopen(OUTPUT,"wt");
date();
for(int i=1;i<=n;i++) if(!ap[i]) {componente++;dfs(i);}
fprintf(fout,"%d",componente);
return 0;
}