Cod sursa(job #1993859)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 23 iunie 2017 22:08:50
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

void visitA(int node, std::vector<std::list<int>> &graph,
    std::vector<bool> &check, std::list<int> &myS) {

    for (int aux : graph[node]) {
        if (!check[aux]) {
            check[aux] = true;
            visitA(aux, graph, check, myS);
        }
    }

    myS.push_back(node);
}

void visitB(int node, std::vector<std::list<int>> &graph,
    std::vector<bool> &check, std::ostream &out) {

    out << node << ' ';
    for (int aux : graph[node]) {
        if (!check[aux]) {
            check[aux] = true;
            visitB(aux, graph, check, out);
        }
    }
}

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

    int nV, nM;

    fileIn >> nV >> nM;

    std::vector<std::list<int>> graph(nV + 1);
    std::vector<std::list<int>> trans(nV + 1);

    int a, b;

    for (int i(0); i < nM; i++) {
        fileIn >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    std::vector<bool> check(nV + 1, false);
    std::list<int> myS;

    for (int i(1); i <= nV; i++) {
        if (!check[i]) {
            check[i] = true;
            visitA(i, graph, check, myS);
        }
    }

    check = std::vector<bool>(nV + 1, false);

    while (!myS.empty()) {

        a = myS.back();
        myS.pop_back();

        if (!check[a]) {
            check[a] = true;
            visitB(a, trans, check, fileOut);
            fileOut << '\n';
        }

    }

    fileIn.close();
    fileOut.close();
    return 0;
}