Cod sursa(job #1411530)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 31 martie 2015 19:31:56
Problema Componente tare conexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using Graph = std::vector<std::vector<int>>;
using Pq = std::priority_queue<std::pair<int, int>>;

void dfs(const Graph &G, int node, std::vector<bool> &visited, Pq &q, int &time)
{
    visited[node] = true;
    for (auto &neigh : G[node])
        if (!visited[neigh])
            dfs(G, neigh, visited, q, ++time);

    q.emplace(++time, node);
}

Pq get_finish_times(const Graph &G)
{
    Pq q;
    std::vector<bool> visited(G.size(), false);
    int time = 0;

    for (auto i = 0u; i < G.size(); ++i)
        if (!visited[i])
            dfs(G, i, visited, q, ++time);

    return q;
}

Graph reverse(const Graph &G)
{
    Graph rvs(G.size());

    for (auto i = 0u; i < G.size(); ++i)
        for (auto &neigh : G[i])
            rvs[neigh].push_back(i);

    return rvs;
}

void dfs_rev(const Graph &G,
             int node,
             Pq &q,
             std::vector<bool> &visited,
             std::vector<std::vector<int>> &ret)
{
    visited[node] = true;
    ret.back().push_back(node);
    q.pop();

    for (auto &neigh : G[node])
        if (!visited[neigh])
            dfs_rev(G, neigh, q, visited, ret);
}

std::vector<std::vector<int>> get_comps(Graph &&G, Pq &&q)
{
    std::vector<bool> visited(G.size(), false);
    std::vector<std::vector<int>> ret;

    while (!q.empty()) {
        ret.push_back(std::vector<int>());
        dfs_rev(G, q.top().second, q, visited, ret);
    }

    return ret;
}

int main()
{
    std::ifstream fin{"ctc.in"};
    std::ofstream fout{"ctc.out"};

    int N, M;
    fin >> N >> M;

    Graph G(N);
    for (auto i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;

        G[x - 1].push_back(y - 1);
    }

    auto ret = get_comps(reverse(G), get_finish_times(G));
    fout << ret.size() << '\n';
    for (auto &comp : ret) {
        for (auto &elem : comp)
            fout << elem + 1 << ' ';
        fout << '\n';
    }

    return 0;
}