Pagini recente » Cod sursa (job #369827) | Rating Ion Ion (ion_ion) | Cod sursa (job #850263) | Cod sursa (job #832292) | Cod sursa (job #147983)
Cod sursa(job #147983)
#include<stdio.h>
#include<string.h>
#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
#define CL(x) memset(x,0,sizeof(x));
FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");
typedef struct elem{
long value;
struct elem *next;
};
elem* p[100001];
long N,M;
int util[100001];
void readValues();
void solveFunction();
void DF(elem*,long);
int main(){
readValues();
solveFunction();
fclose(fin);
fclose(fout);
return 0;
}
void readValues(){
fscanf(fin, "%ld %ld", &N, &M);
long val1,val2;
elem *adr;
for(long i=1;i<=M;++i){
fscanf(fin, "%ld %ld", &val1, &val2);
adr=new elem;
adr->value=val2;
adr->next=p[val1];
p[val1]=adr;
adr=new elem;
adr->value=val1;
adr->next=p[val2];
p[val2]=adr;
}
}
void solveFunction(){
CL(util);
long final=0;
for(long i=1;i<=N;++i){
if(!util[i]){
++final;
DF(p[i],i);
}
}
fprintf(fout, "%ld\n", final);
}
void DF(elem *ad,long poz){
elem *adr;
adr=ad;
util[poz]=1;
while(adr!=NULL){
if(!util[adr->value])
DF(adr,adr->value);
adr=adr->next;
}
}