Cod sursa(job #1041933)

Utilizator arch_enemyAngela Gossow arch_enemy Data 26 noiembrie 2013 13:21:40
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define NMAX 100001

using namespace std;

int N, M, i, node1, node2, CC;
vector<int> G[NMAX];
bool Used[NMAX];

inline void DFS(int Node) {
    Used[Node] = true;

    for(vector<int>::iterator AdjNode = G[Node].begin(); AdjNode != G[Node].end(); ++AdjNode)
        if(!Used[*AdjNode])
            DFS(*AdjNode);
}

int main() {
    freopen("prep.in", "r", stdin);
    freopen("prep.out", "w", stdout);

    scanf("%d%d", &N, &M);
    while(M--) {
        scanf("%d%d", &node1, &node2);
        G[node1].push_back(node2);
        G[node2].push_back(node1);
    }

    memset(Used, false, sizeof(bool));
    for(i = 1; i <= N; ++i)
        if(!Used[i]) {
            ++CC;
            DFS(i);
        }

    printf("%d\n", CC);

    return 0;
}