Cod sursa(job #790671)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 22 septembrie 2012 00:35:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <vector>

using namespace std;

const int MaxN = 100005;

vector <int> G[MaxN];
int N, CC[MaxN];

void DFS(int X) {
    CC[X] = CC[0];
    for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y)
        if (!CC[*Y])
            DFS(*Y);
}

void Solve() {
    for (int X = 1; X <= N; ++X) {
        if (!CC[X]) {
            ++CC[0]; DFS(X);
        }
    }
}

void Read() {
    freopen("dfs.in", "r", stdin);
    int M; scanf("%d %d", &N, &M);
    for (; M; --M) {
        int X, Y; scanf("%d %d", &X, &Y);
        G[X].push_back(Y), G[Y].push_back(X);
    }
}

void Print() {
    freopen("dfs.out", "w", stdout);
    printf("%d\n", CC[0]);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}