Cod sursa(job #1656135)

Utilizator wilversingsMarius Aiordachioaei wilversings Data 18 martie 2016 19:55:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstdlib>

using namespace std;

const int NMAX = 100003;

vector<int> *graph;
bitset<NMAX> checked;

void DFS (const int node) {

    checked[node] = true;

    for (auto i : graph[node])
        if (!checked[i])
            DFS(i);

}

int main () {

    freopen ("dfs.in", "r", stdin);
    freopen ("dfs.out", "w", stdout);

    int N, M, ans = 0;

    scanf ("%d%d", &N, &M);

    graph = new vector<int>[N + 1];

    while (M--) {
        int a, b;
        scanf ("%d%d", &a, &b);

        graph[a].push_back (b);
        graph[b].push_back (a);

    }

    for (int i = 1; i <= N; ++i)
    if (!checked[i]) {
        DFS(i);
        ++ans;
    }

    printf ("%d", ans);

}