Cod sursa(job #605046)

Utilizator SpiderManSimoiu Robert SpiderMan Data 26 iulie 2011 16:58:42
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
# include <cstdio>
# include <vector>
using namespace std;

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

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

void dfs (int S) {
    VIZ[S] = 1;
    for (int i = 1; i <= G[S][0]; ++i)
        if (VIZ[G[S][i]] == 0)
            dfs (G[S][i]);
}
int main (void) {
    freopen (FIN, "r", stdin);

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