Cod sursa(job #672039)

Utilizator SpiderManSimoiu Robert SpiderMan Data 1 februarie 2012 14:39:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
# include <cstdio>

const char *FIN = "dfs.in", *FOU = "dfs.out";
const int MAX = 100005;

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

int N, M, sol, VIZ[MAX];
gr *G[MAX];

inline void add (int a, int b) {
    gr *aux = new gr;
    aux -> nod = b;
    aux -> next = G[a];
    G[a] = aux;
}

void dfs (int S) {
    VIZ[S] = 1;
    for (gr *it = G[S]; it != NULL; it = it -> next)
        if (VIZ[it -> nod] == 0)
            dfs (it -> nod);
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        add (x, y), add (y, x);
    }
    for (int i = 1; i <= N; ++i)
        if (VIZ[i] == 0)
            ++sol, dfs (i);

    fprintf (fopen (FOU, "w"), "%d", sol);
}