Cod sursa(job #1163433)

Utilizator SRaduRadu Szasz SRadu Data 1 aprilie 2014 12:55:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>

using namespace std;

const int MAX = 100005;

int N, M;
vector<int> G[MAX];
bool Visited[MAX];

void citire() {
    ifstream in("dfs.in");
    in >> N >> M;
    for(int i = 1, A, B; i <= M; i++) {
        in >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    } in.close();
}

void dfs(int nod) {
    Visited[nod] = true;
    for(size_t i = 0; i < G[nod].size(); i++) {
        int dest = G[nod][i];
        if(!Visited[dest])
            dfs(dest);
    }
}

void afisare() {
    int Ans = 0;
    for(int i = 1; i <= N; i++) {
        if(!Visited[i]) {
            dfs(i);
            Ans++;
        }
    }
    ofstream out("dfs.out");
    out << Ans << "\n";
    out.close();
}

int main() {
    citire();
    afisare();
}