Cod sursa(job #2699595)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 25 ianuarie 2021 09:26:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1e5+5;

vector <int> w[NMAX];
int nivel[NMAX], nivmin[NMAX];
stack < pair <int, int> > stiva;
vector < vector <int> > sol;

void retin(int a, int b){
    pair <int, int> aux, stop;
    stop = {a, b};
    vector <int> vec;
    while(true){
        aux = stiva.top();
        stiva.pop();
        vec.push_back(aux.first);
        vec.push_back(aux.second);
        if(aux == stop)
            break;
    }

    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    sol.push_back(vec);
}

void DFS(int nod, int t){

    nivmin[nod] = nivel[nod] = nivel[t] + 1;
    int nrel = w[nod].size();
    for(int i = 0; i < nrel; ++i){
        int vecin = w[nod][i];
        if(vecin == t)
            continue;

        if(!nivel[vecin]){
            stiva.push({nod, vecin});
            DFS(vecin, nod);
            nivmin[nod] = min(nivmin[nod], nivmin[vecin]);

            if(nivmin[vecin] >= nivel[nod])
                retin(nod, vecin);
        }
        else nivmin[nod] = min(nivmin[nod], nivel[vecin]);
    }
}

int main()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n, m, i;
    fin >> n >> m ;
    for(i = 1; i <= m; ++i){
        int a, b;
        fin >> a >> b;
        w[a].push_back(b);
        w[b].push_back(a);
    }

    DFS(1, 0);

    int nrsol = sol.size();
    fout << nrsol << '\n';
    for(i = 0; i < nrsol; ++i){
        int nrel = sol[i].size();
        for(int j = 0; j < nrel; ++j){
            fout << sol[i][j] << ' ';
        }
        fout << '\n';
    }

    return 0;
}