Cod sursa(job #1895010)

Utilizator andreinmAndrei andreinm Data 27 februarie 2017 18:43:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

const int NM = 100010;

vector <int> G[NM];
bool visited[NM];
int cnt, N, E, node, X, Y;


void Visit(int node) {
    visited[node] = 1;
    for (auto &it: G[node]) {
        if (!visited[it])
        Visit(it);
    }
}

int main()
{
    in >> N >> E;
    for (node = 1; node <= E; ++node) {
        in >> X >> Y;
        G[X].push_back(Y);
        G[Y].push_back(X);
    }

    for (node = 1; node <= N; ++node) {
        if (!visited[node]){
            Visit(node);
            cnt++;
        }
    }

    out << cnt;

    return 0;
}