Cod sursa(job #2224742)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 24 iulie 2018 21:54:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

typedef vector<vector<int>> Graph;

const string IN_FILE = "ctc.in";
const string OUT_FILE = "ctc.out";

void dfp(const Graph& G, const int u, vector<int>& sign, vector<int>& order) {
    sign[u] = 1;
    for (const auto& v : G[u]) {
        if (sign[v] == 0) {
            dfp(G, v, sign, order);
        }
    }
    order.push_back(u);
}

void dfm(const Graph& GT, const int v, vector<int>& sign, vector<int>& comp) {
    sign[v] = -1;
    comp.push_back(v);
    for (const auto&u : GT[v]) {
        if (sign[u] == 1) {
            dfm(GT, u, sign, comp);
        }
    }
}

Graph transpose(const Graph& G) {
    const int size = int(G.size());
    auto GT = Graph(size);
    for (int u = 0; u < size; u++) {
        for (const auto& v : G[u]) {
            GT[v].push_back(u);
        }
    }
    return GT;
}

vector<vector<int>> kosaraju(const Graph& G) {
    const int size = int(G.size());
    const auto GT = transpose(G);
    auto sign = vector<int>(size);
    auto order = vector<int>();
    for (int u = 0; u < size; u++) {
        if (sign[u] == 0) {
            dfp(G, u, sign, order);
        }
    }
    reverse(order.begin(), order.end());
    auto components = vector<vector<int>>();
    for (const auto& u : order) {
        if (sign[u] == 1) {
            auto comp = vector<int>();
            dfm(GT, u, sign, comp);
            components.push_back(comp);
        }
    }
    return components;
}

Graph readGraph() {
    ifstream in(IN_FILE);
    int V, E;
    in >> V >> E;
    auto G = Graph(V);
    for (int i = 0; i < E; i++) {
        int u, v;
        in >> u >> v;
        G[u - 1].push_back(v - 1);
    }
    in.close();
    return G;
}

void writeComponents(const vector<vector<int>>& components) {
    ofstream out(OUT_FILE);
    out << int(components.size()) << "\n";
    for (const auto& comp : components) {
        for (int i = 0; i < int(comp.size()); i++) {
            out << comp[i] + 1 << (i + 1 < int(comp.size()) ? " " : "\n");
        }
    }
    out.close();
}

int main() {
    const auto G = readGraph();
    const auto components = kosaraju(G);
    writeComponents(components);
    return 0;
}