Cod sursa(job #1154225)

Utilizator SpiderManSimoiu Robert SpiderMan Data 26 martie 2014 00:56:31
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
# include <cstdio>
# include <stack>
# include <vector>
using namespace std;

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

int N, M, sol, viz[MAX];
vector <int> G[MAX];
int st[MAX];

void dfs (int S) {
    viz[S] = 1, st[0] = 0;
    for (auto &it: G[S])
        st[++st[0]] = it, viz[it] = 1;
    for (; st[0] > 0; ) {
        int node = st[st[0]--];
        for (auto &it: G[S])
            if (viz[it] == 0)
                viz[it] = 1, st[++st[0]] = it;
    }
}

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);
        G[x].push_back (y);
        G[y].push_back (x);
    }
    for (int i = 1; i <= N; ++i)
        if (viz[i] == 0)
            ++sol, dfs (i);
    fprintf (fopen (FOU, "w"), "%d", sol);
}