Cod sursa(job #209990)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 25 septembrie 2008 21:52:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#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;



}