Cod sursa(job #1790598)

Utilizator preda.andreiPreda Andrei preda.andrei Data 28 octombrie 2016 15:10:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
#include <vector>

using namespace std;

struct Nod
{
    int timp;
    int timp_min;
    vector<int> vecini;
};

typedef vector<Nod> Graf;
typedef pair<int, int> Muchie;

int TIMP = 0;

vector<int> ExtrageComponenta(vector<Muchie> &st, const Muchie &m)
{
    vector<int> comp;
    while (st.back() != m) {
        comp.push_back(st.back().second);
        st.pop_back();
    }
    comp.push_back(m.second);
    comp.push_back(m.first);
    st.pop_back();
    return comp;
}

void Tarjan(Graf &g, int nod, vector<Muchie> &st, vector<vector<int>> &comp)
{
    g[nod].timp = g[nod].timp_min = ++TIMP;
    for (int vecin : g[nod].vecini) {
        if (g[vecin].timp == 0) {
            st.push_back({nod, vecin});
            Tarjan(g, vecin, st, comp);

            g[nod].timp_min = min(g[nod].timp_min, g[vecin].timp_min);
            if (g[vecin].timp_min >= g[nod].timp)
                comp.push_back(ExtrageComponenta(st, {nod, vecin}));
        }
        g[nod].timp_min = min(g[nod].timp_min, g[vecin].timp);
    }
}

vector<vector<int>> AflaComponente(Graf &g)
{
    for (auto &nod : g)
        nod.timp = nod.timp_min = 0;

    vector<vector<int>> comp;
    vector<Muchie> stiva;
    Tarjan(g, 1, stiva, comp);

    return comp;
}

int main()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.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);
        graf[y].vecini.push_back(x);
    }

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

    return 0;
}