Cod sursa(job #147458)

Utilizator moga_florianFlorian MOGA moga_florian Data 2 martie 2008 22:01:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#define Nmax 100005

struct nod{int vec;nod* next;};
typedef nod* list;
list a[Nmax];
char viz[Nmax];

void dfs(int x){

    viz[x] = 1;
    for(list p = a[x];p;p=p->next)
        if(viz[p->vec]==0)
            dfs(p->vec);

}

int main(){

    FILE *fin =fopen("dfs.in","r"),
         *fout =fopen("dfs.out","w");
         
    int N,M;
    fscanf(fin,"%d%d",&N,&M);
    
    for(int i=0;i<M;i++){
        int x,y;
        fscanf(fin,"%d%d",&x,&y);
        
        list aux = new nod;
        aux -> vec = y;
        aux -> next = a[x];
        a[x] = aux;
        
        aux = new nod;
        aux -> vec = x;
        aux -> next = a[y];
        a[y] = aux;
    }
    
    int sol = 0;
    
    for(int i=1;i<=N;i++)
        if(viz[i] == 0){
            sol ++;
            dfs(i);
        }

    fprintf(fout,"%d\n",sol);
    fclose(fin);
    fclose(fout);
    return 0;
}