Cod sursa(job #3288497)

Utilizator elisa.ipateElisa Ipate elisa.ipate Data 22 martie 2025 15:34:35
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax = 1e5 + 1;
int adancime[nmax], adancime_min[nmax], parent[nmax];
vector <int> edges[nmax], stack_muchii, aux;
vector <vector <int>> comp_biconexe;

void dfs( int vf, int parinte ) {
    parent[vf] = parinte;
    //cout << vf << "VF\n";
    adancime[vf] = adancime[parinte] + 1;
    for( int copil: edges[vf] ) {
        if( copil == parinte )
            continue;
        if (adancime[copil] != 0)
            continue;
        stack_muchii.push_back(copil);
        dfs( copil, vf );
        if( adancime_min[copil] >= adancime[vf] ) {
            //cout << copil << " " << vf << "\n";
            aux.clear();
            while( stack_muchii.back() != copil ) {
                //cout << stack_muchii.back() << "aux ";
                aux.push_back(stack_muchii.back());
                stack_muchii.pop_back();
            }
            aux.push_back(copil);
            if( !aux.empty() )
                comp_biconexe.push_back(aux);
        }
    }
    adancime_min[vf] = adancime[vf];
    for( int copil: edges[vf] ) {
        if (copil == parinte)
            continue;
        if( adancime_min[copil] == 0 )
            adancime_min[vf] = min(adancime_min[vf], adancime[copil]);
        else
            adancime_min[vf] = min( adancime_min[vf], adancime_min[copil] );
    }
    //cout << vf << " " << adancime_min[vf] << "\n";
}

int main() {
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int n, m;
    cin >> n >> m;
    for( int i = 1; i <= m; i++ ) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs( 1, 0 );
    cout << comp_biconexe.size() << "\n";
    for( vector <int> x: comp_biconexe ) {
        vector <int> y = x;
        for( int i = 0; i < x.size(); i++ )
            y.push_back(parent[x[i]]);
        sort( y.begin(), y.end() );
        cout << y[0] << " ";
        for( int i = 1; i < y.size(); i++ )
            if( y[i] != y[i - 1] )
                cout << y[i] << " ";
        cout << "\n";
    }
}