Cod sursa(job #204761)

Utilizator moga_florianFlorian MOGA moga_florian Data 26 august 2008 20:24:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#define Nmax 100005

struct nod{int vec;nod* next;};
typedef nod* list;
list a[Nmax];
char viz[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);    
        }
   
}

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++;
            dfs(i);
        }
    
    fprintf(fout,"%d\n",cc);
    fclose(fin);
    fclose(fout);
    return 0;
       
}