Cod sursa(job #754486)

Utilizator MarquiseMarquise Marquise Data 2 iunie 2012 11:24:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#define NMAX 100001

struct nod
{
       int info;
       nod *next; 
};

nod *v[NMAX];
int n, m, componente, viz[NMAX];

void adaug(int x, int y)
{
     nod *aux;
     aux = new nod;
     aux -> info = y;
     aux -> next = v[x];
     v[x] = aux;
}

void dfs(int x)
{
     nod *p;
     
     viz[x] = 1;
     for ( p = v[x]; p; p = p -> next)
         if ( viz[p->info] == 0)
            dfs(p->info);
}

int main()
{
    int i, x, y;
    
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for ( i = 1; i <= m; i++)
    {
        scanf("%d %d", &x, &y);
        adaug(x, y);
        adaug(y, x);
    }
    
    for ( i = 1; i <= n; i++)
        if ( viz[i] == 0)
        {
             componente++;
             dfs(i);
        }
    
    printf("%d\n", componente);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}