Cod sursa(job #3348756)

Utilizator MMEnisEnis Mutlu MMEnis Data 23 martie 2026 20:31:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

const int NMAX = 1e5 + 1;

vector <int> adj[NMAX];
int parent[NMAX];
int tin[NMAX], tmin[NMAX];
int t = 0;
stack <int> st;
vector <vector <int>> sol;

void add_biconex ( int nod, int nod_spate )
{
    vector <int> comp;
    while ( st.size() && st.top() != nod_spate )
    {
        comp.push_back(st.top());
        st.pop();
    }
    comp.push_back(st.top());
    st.pop();
    comp.push_back(nod);
    sol.push_back(comp);
}

void dfs ( int nod, int parent )
{
    tin[nod] = tmin[nod] = ++ t;
    st.push(nod);
    for ( auto it : adj[nod] )
    {
        if ( it == parent )
            continue;
        if ( !tin[it] )
        {
            dfs ( it, nod );
            tmin[nod] = min ( tmin[nod], tmin[it] );
            if ( tmin[it] >= tin[nod] )
                add_biconex( nod, it );
        }
        else tmin[nod] = min ( tmin[nod], tin[it] );
    }
}

int main()
{
    int n, m;
    f >> n >> m;
    for ( int i = 1; i <= m; i ++ )
    {
        int u, v;
        f >> u >> v;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    dfs ( 1, 0 );
    g << sol.size() << '\n';
    for ( auto v : sol )
    {
        for ( auto it : v )
            g << it << " ";
        g << '\n';
    }
    return 0;
}