Cod sursa(job #1413482)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 1 aprilie 2015 21:46:08
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using Graph = std::vector<std::vector<int>>;



const int NMAX = 100005;

Graph G(NMAX);
std::vector<int> indexes(NMAX, -1);
std::vector<int> lowlinks(NMAX);
std::vector<bool> onstack(NMAX);

void tarjan(int node,
            std::vector<std::vector<int>> &comps,
            std::stack<int> &st,
            int &curr_idx)
{
    ++curr_idx;
    indexes[node] = lowlinks[node] = curr_idx;
    st.emplace(node);
    onstack[node] = true;

    for (auto &neigh : G[node]) {
        if (indexes[neigh] == -1) {
            tarjan(neigh, comps, st, curr_idx);
            lowlinks[node] = std::min(lowlinks[node], lowlinks[neigh]);
        } else {
            lowlinks[node] = std::min(lowlinks[node], lowlinks[neigh]);
        }
    }

    if (indexes[node] == lowlinks[node]) {
        std::vector<int> comp;
        int curr = -1;

        while (!st.empty() && curr != node) {
            curr = st.top();
            st.pop();

            onstack[curr] = false;
            comp.emplace_back(curr);
        }

        comps.emplace_back(comp);
    }
}

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

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

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

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

    std::vector<std::vector<int>> comps;
    int start_idx = 0;
    std::stack<int> st;

    for (auto i = 0; i < N; ++i)
        if (indexes[i] == -1)
            tarjan(i, comps, st, start_idx);

    fout << comps.size() << '\n';
    for (auto &comp : comps) {
        for (auto &elem : comp)
            fout << elem + 1 << ' ';
        fout << '\n';
    }

    return 0;
}