Cod sursa(job #2652002)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 24 septembrie 2020 02:59:55
Problema Componente biconexe Scor 88
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m, nivel[100005], mn[100005], stiva[100005], nr, tr;
bool fost[100005];
vector<int> vecini[100005], sol[100005];
stack <pair <int, int> > stk;

void dfs ( int nod, int tata )
{
    fost[nod] = 1;
    nivel[nod] = nivel[tata] + 1;
    mn[nod] = nivel[nod];

    for ( int i = 0; i < vecini[nod].size(); i++ )
        if ( vecini[nod][i] != tata )
        {
            if ( fost[vecini[nod][i]] ) mn[nod] = min ( mn[nod], nivel[vecini[nod][i]] );
            else
            {
                dfs ( vecini[nod][i], nod );
                mn[nod] = min ( mn[nod], mn[vecini[nod][i]] );
            }
        }
}

void solve ( int nod, int tata )
{
    fost[nod] = 1;
    for ( int i = 0; i < vecini[nod].size(); i++ )
        if ( !fost[vecini[nod][i]] )
        {
            stk.push( make_pair(nod,vecini[nod][i]) );
            solve ( vecini[nod][i], nod );

            if ( mn[ vecini[nod][i] ] >= nivel[ nod ] )
            {
                tr++;

                while ( stk.top().first != nod )
                {
                    sol[tr].push_back ( stk.top().first );
                    sol[tr].push_back ( stk.top().second );
                    stk.pop();
                }
                sol[tr].push_back ( stk.top().first );
                sol[tr].push_back ( stk.top().second );
                stk.pop();
            }
        }
}

int main()
{
    f >> n >> m;

    for ( int i = 1; i <= m; i++ )
    {
        int x, y;
        f >> x >> y;
        vecini[x].push_back ( y );
        vecini[y].push_back ( x );
    }

    dfs ( 1, 0 );

    for ( int i = 1; i <= n; i++ ) fost[i] = 0;

    solve ( 1, 0 );
///for(int i=1;i<=n;i++) cout<<mn[i]<<' ';
    g << tr << '\n';

    while ( tr )
    {
        int v[100005];

        for ( int i = 0; i < sol[tr].size(); i++ ) v[i] = sol[tr][i];

        sort ( v, v + sol[tr].size() );

        for ( int i = 0; i < sol[tr].size(); i++ ) if( v[i]!=v[i-1] ) g << v[i] << ' ';

        tr--;
        g << '\n';
    }
}