Pagini recente » Cod sursa (job #2398879) | Cod sursa (job #2054263) | Cod sursa (job #1618048) | Cod sursa (job #576713) | Cod sursa (job #161509)
Cod sursa(job #161509)
#include <stdio.h>
#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
int ap[100005],n,m,componente;
typedef struct nod {
int x;
nod *a;
} *pNod;
pNod g[100005];
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;
}