Cod sursa(job #1638173)

Utilizator cautionPopescu Teodor caution Data 7 martie 2016 21:36:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

constexpr int kMaxN = 100000;

int n, m;
std::vector<int> edges[kMaxN+1];
std::vector<std::vector<int> > strongly_connected_components;
bool on_stack[kMaxN+1];
int predecesor[kMaxN+1], index[kMaxN+1], static_index;
std::stack<int> S;

void computeScc(int x)
{
    ++static_index;
    index[x] = static_index;
    predecesor[x] = index[x];
    on_stack[x] = true;
    S.push(x);
    for(auto y : edges[x]) {
        if(index[y] == 0) {
            computeScc(y);
            predecesor[x] = std::min(predecesor[x], predecesor[y]);
        }
        else if(on_stack[y]) {
            predecesor[x] = std::min(predecesor[x], index[y]);
        }
    }
    if(predecesor[x] == index[x]) {
        std::vector<int> scc;
        while(S.top() != x) {
            scc.push_back(S.top());
            on_stack[S.top()] = false;
            S.pop();
        }
        scc.push_back(x);
        on_stack[x] = false;
        S.pop();
        strongly_connected_components.push_back(std::move(scc));
    }
}

void computeTarjan()
{
    for(int i = 1; i <= n; ++i) {
        if(index[i] == 0) computeScc(i);
    }
}

int main()
{
    std::ifstream in("ctc.in");
    std::ofstream out("ctc.out");
    in>>n>>m;
    for(int x, y, i = 1; i <= m; ++i) {
        in>>x>>y;
        edges[x].push_back(y);
    }
    computeTarjan();
    out<<strongly_connected_components.size()<<'\n';
    for(auto scc : strongly_connected_components) {
        for(auto x : scc) out<<x<<' ';
        out<<'\n';
    }
    return 0;
}