Cod sursa(job #2197858)

Utilizator horiahoria1Horia Alexandru Dragomir horiahoria1 Data 22 aprilie 2018 23:05:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <vector>
#include <stack>

void print_output(std::vector<std::vector<int>> result, std::ofstream &out) {

    out << result.size() << '\n';
    for (auto &ctc : result) {
        for (auto &node : ctc) {
            out << node << ' ';
        }
        out << '\n';
    }

}

void dfs(int node, std::vector<int> *adj,std::vector<bool> &visited,
         std::stack<int> &kosaraju) {

    visited[node] = true;
    for (auto &neighbour : adj[node]) {
        if (!visited[neighbour]) {
            dfs(neighbour, adj, visited, kosaraju);
        }
    }
    kosaraju.push(node);

}

void dfs_transpose(int node, std::vector<int> *adj_transpose,
                   std::vector<bool> &visited_transpose, std::vector<int> &ctc) {

    ctc.push_back(node);
    visited_transpose[node] = false;
    for (auto &neighbour : adj_transpose[node]) {
        if (visited_transpose[neighbour]) {
            dfs_transpose(neighbour, adj_transpose, visited_transpose, ctc);
        }
    }

}

int main() {

    std::ifstream in("ctc.in");
    std::ofstream out("ctc.out");

    int n, m;
    in >> n >> m;

    std::vector<int> adj[n + 1];
    std::vector<int> adj_transpose[n + 1];

    int i;
    int u, v;

    for (i = 0; i < m; ++i) {
        in >> u >> v;
        adj[u].push_back(v);
        adj_transpose[v].push_back(u);
    }

    std::stack<int> kosaraju;

    std::vector<bool> visited(n + 1, false);

    for (i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs(i, adj, visited, kosaraju);
        }
    }

    std::vector<std::vector<int>> result;

    while (!kosaraju.empty()) {
        int node = kosaraju.top();
        kosaraju.pop();
        if (visited[node]) {
            std::vector<int> new_ctc;
            dfs_transpose(node, adj_transpose, visited, new_ctc);
            result.push_back(new_ctc);
        }
    }

    print_output(result, out);

    in.close();
    out.close();

    return 0;
}