Pagini recente » Cod sursa (job #387340) | Cod sursa (job #1181874) | Cod sursa (job #1528992) | Cod sursa (job #962037) | Cod sursa (job #209990)
Cod sursa(job #209990)
#include<stdio.h>
FILE *fin=fopen("dfs.in","r"),
*fout=fopen("dfs.out","w");
int N,M;
struct nod{int vec;nod* next;};
typedef nod* lista;
lista L[100010];
int graf[100010];
char uz[100010];
int Q[100010];
int main(){
fscanf(fin,"%d %d",&N,&M);
for(int i=1;i<=N;i++){
L[i]=new nod;
L[i]=NULL;
}
for(int i=1;i<=M;i++){
int x,y;
fscanf(fin,"%d %d",&x,&y);
lista aux;
aux=new nod;
aux->vec=y;
aux->next=L[x];
L[x]=aux;
aux=new nod;
aux->vec=x;
aux->next=L[y];
L[y]=aux;
}
int cat=0;
for(int i=1;i<=N;i++)
if(graf[i]==0){
graf[i]=++cat;
int li,lf;
li=1,lf=1;
Q[1]=i;
uz[i]=1;
while(li<=lf){
graf[Q[li]]=cat;
for(lista p=L[Q[li]];p;p=p->next)
if(uz[p->vec]==0){
Q[++lf]=p->vec;
uz[p->vec]=1;
}
++li;
}
}
/*
for(int i=1;i<=N;i++)
fprintf(fout,"%d ",graf[i]);
*/
fprintf(fout,"%d\n",cat);
fclose(fin);
fclose(fout);
return 0;
}