Cod sursa(job #1990017)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 9 iunie 2017 22:59:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>

void visit(std::vector<bool> &check, std::vector<int> *vertices, int curr) {
    check[curr] = true;
    for (int vertex : vertices[curr]) {
        if (!check[vertex]) {
            visit(check, vertices, vertex);
        }
    }
}

int main() {
    std::ifstream fileIn("dfs.in");
    std::ofstream fileOut("dfs.out");

    int nV, nE;

    fileIn >> nV >> nE;

    std::vector<int> *vertices = new std::vector<int>[nV + 1]();
    std::vector<bool> check(nV + 1, false);

    int from, to;
    for (int i(0); i < nE; i++) {
        fileIn >> from >> to;
        vertices[from].push_back(to);
        vertices[to].push_back(from);
    }

    int vCount(0);
    for (int i(1); i <= nV; i++) {
        if (!check[i]) {
            vCount++;
            visit(check, vertices, i);
        }
    }

    fileOut << vCount;

    delete[] vertices;
    fileIn.close();
    fileOut.close();
    return 0;
}