Cod sursa(job #204762)

Utilizator moga_florianFlorian MOGA moga_florian Data 26 august 2008 20:26:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#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;
       
}