Pagini recente » Cod sursa (job #1735658) | Cod sursa (job #2621438) | Cod sursa (job #760797) | Cod sursa (job #1109527) | Cod sursa (job #204762)
Cod sursa(job #204762)
#include<stdio.h>
#define Nmax 100005
struct nod{int vec;nod* next;};
typedef nod* list;
list a[Nmax];
char viz[Nmax];
int Q[Nmax];
void adauga(int x,int y){
list aux = new nod;
aux->vec=y;
aux->next=a[x];
a[x]=aux;
}
void dfs(int i){
for(list p = a[i];p;p=p->next)
if(viz[p->vec]==0){
viz[p->vec]=1;
dfs(p->vec);
}
}
void bfs(int i){
int li,lf;
li=lf=1;
Q[li]=i;
while(li<=lf){
for(list p=a[Q[li]];p;p=p->next)
if(viz[p->vec]==0){
viz[p->vec]=1;
Q[++lf]=p->vec;
}
li++;
}
}
int main(){
FILE *fin = fopen("dfs.in","r");
FILE *fout=fopen("dfs.out","w");
int N,M;
fscanf(fin,"%d%d",&N,&M);
for(int i=1;i<=M;i++){
int x,y;
fscanf(fin,"%d%d",&x,&y);
adauga(x,y);
adauga(y,x);
}
int cc=0;
for(int i=1;i<=N;i++)
if(viz[i]==0){
cc++;
bfs(i);
}
fprintf(fout,"%d\n",cc);
fclose(fin);
fclose(fout);
return 0;
}