Cod sursa(job #1993866)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 23 iunie 2017 22:13:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 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::list<int> &out) {

    out.push_back(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);
    std::list<std::list<int>> out;

    while (!myS.empty()) {

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

        if (!check[a]) {
            check[a] = true;
            out.push_back(std::list<int>());
            visitB(a, trans, check, out.back());
        }

    }

    fileOut << out.size() << '\n';

    for (std::list<int> strong : out) {
        for (int vertex : strong) {
            fileOut << vertex << ' ';
        }
        fileOut << '\n';
    }

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