Cod sursa(job #1790489)

Utilizator preda.andreiPreda Andrei preda.andrei Data 28 octombrie 2016 12:14:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <vector>

using namespace std;

struct Nod
{
    int timp = 0;
    int timp_minim = 0;
    bool in_stiva;
    vector<int> vecini;
};

typedef vector<Nod> Graf;

int TIMP = 0;

void Tarjan(Graf &g, int start, vector<int> &st, vector<vector<int>> &ctc)
{
    g[start].timp = g[start].timp_minim = ++TIMP;
    st.push_back(start);
    g[start].in_stiva = true;

    for (int vecin : g[start].vecini) {
        if (g[vecin].timp == 0)
            Tarjan(g, vecin, st, ctc);
        if (g[vecin].in_stiva)
            g[start].timp_minim = min(g[start].timp_minim, g[vecin].timp_minim);
    }

    if (g[start].timp_minim == g[start].timp) {
        vector<int> comp;
        do {
            comp.push_back(st.back());
            g[st.back()].in_stiva = false;
            st.pop_back();
        } while (comp.back() != start);

        ctc.push_back(comp);
    }
}

vector<vector<int>> AflaCTC(Graf &g)
{
    vector<vector<int>> componente;
    for (unsigned i = 1; i < g.size(); ++i) {
        if (g[i].timp == 0) {
            vector<int> stiva;
            Tarjan(g, i, stiva, componente);
        }
    }
    return componente;
}

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

    int n, m;
    fin >> n >> m;

    Graf graf(n + 1);
    while (m--) {
        int x, y;
        fin >> x >> y;
        graf[x].vecini.push_back(y);
    }

    auto componente = AflaCTC(graf);
    fout << componente.size() << "\n";
    for (auto &comp : componente) {
        for (int nod : comp)
            fout << nod << " ";
        fout << "\n";
    }

    return 0;
}