Cod sursa(job #1028372)

Utilizator tsubyRazvan Idomir tsuby Data 13 noiembrie 2013 22:11:44
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#define NMAX 100005

int n, m, viz[NMAX], nr_componente_conexe; /// n noduri, m muchii

struct nod
{
    int x;
    nod *a;
};

typedef nod *pNod;
pNod v[NMAX];

void add(pNod &dest, int val)
{
    pNod p = new nod;
    p -> x = val;
    p -> a = dest;
    dest = p;
}

void DFS(int nod)
{
    pNod p;
    viz[nod] = 1;
    for (p = v[nod]; p != NULL; p = p -> a)
        if (!viz[p -> x])
            DFS(p -> x);
}
void prelucrare()
{
    for(int i = 1; i <= n; i++)
        if (!viz[i])
        {
            nr_componente_conexe++;
            DFS(i);
        }
    printf("%d\n",nr_componente_conexe);
}

int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    scanf("%d %d", &n, &m);
    int x, y;
    for(int i = 0; i < m; i++)
    {
        scanf("%d %d", &x, &y);
        add(v[x], y);
        add(v[y], x);
    }
    prelucrare();
    return 0;
}