Cod sursa(job #640709)

Utilizator cristian9Cristian Zloteanu cristian9 Data 26 noiembrie 2011 13:04:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<stdio.h>

int n, viz[100001], m;

struct nod{
    int info;
    nod *adr;
} *v[100005];

void push(int a, int b){
    nod *tmp=new nod;
    tmp->info=b;
    tmp->adr=v[a];
    v[a]=tmp;
}

void parcurgere (int k){
    nod* curs=v[k];
    while(curs!=NULL)
    {
        if(viz[curs->info]==0){
            viz[curs->info]=1;
            parcurgere(curs->info);
        }
            curs=curs->adr;
    }
}

int main(){
    freopen ("dfs.in", "r", stdin);
    freopen ("dfs.out", "w", stdout);

    int x, y, c=0, i;
    scanf("%d %d ", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d %d ", &x, &y);
        push (x, y);
        push (y, x);
    }
    for(i=1; i<=n; i++)
        if(viz[i]==0)
        {
            viz[i]=1;
            parcurgere(i);
            c++;
        }
    printf("%d ", c);
    return 0;
}