Cod sursa(job #152126)

Utilizator raula_sanChis Raoul raula_san Data 9 martie 2008 01:30:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>

#define dim 100001

int N;
int M;

char U[dim];

struct Nod
{
    int n;
    Nod *next;
    
} *G[dim];

void Add(Nod *&g, int n)
{
    Nod *p = new Nod;
    p -> n = n;
    p -> next = g;
    g = p;
}

void Df(int nd)
{
    U[nd] = 1;

    for(Nod *p=G[nd]; p; p=p->next)
        if(!U[p->n]) Df(p->n);
}

int main()
{
    freopen("dfs.in", "rt", stdin);
    freopen("dfs.out", "wt", stdout);

    int a, b;
    for(scanf("%d %d", &N, &M); M; --M)
    {
        scanf("%d %d", &a, &b);
        Add(G[a], b);
        Add(G[b], a);
    }

    int ret = 0;
    int i;
    for(i=1; i<=N; ++i)
        if(!U[i])
        {
            Df(i);
            ++ ret;
        }

    printf("%d", ret);

    fclose(stdin);
    fclose(stdout);

    return 0;
}