Cod sursa(job #2530740)

Utilizator Rares31100Popa Rares Rares31100 Data 25 ianuarie 2020 11:20:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m;

vector <int> gf[100001];
int nivel[100001],minNivel[100001];
bitset <100001> viz;
int stiva[100001],nrc;
vector <int> sol[100001];
int nrs;

void dfsBic(int nod,int from,int niv=1)
{
    viz[nod]=1;
    nivel[nod]=niv;
    minNivel[nod]=niv;

    stiva[++nrc]=nod;

    for( auto vec:gf[nod] )
        if( vec != from && viz[vec] )
        {
            minNivel[nod]=min( minNivel[nod], nivel[vec] ); //muchiile de intoarcere
        }
        else if( vec != from )
        {
            dfsBic( vec, nod, niv+1 );
            minNivel[nod]=min( minNivel[nod], minNivel[vec] );

            if( nivel[nod] <= minNivel[vec] )
            {
                nrs++;
                while( stiva[nrc] != vec )
                    sol[nrs].push_back( stiva[nrc--] );

                sol[nrs].push_back( stiva[nrc--] );
                sol[nrs].push_back( nod );
            }
        }
}

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

    for(int i,j,k=1;k<=m;k++)
    {
        in>>i>>j;

        gf[i].push_back(j);
        gf[j].push_back(i);
    }

    dfsBic(1,0);

    out<<nrs<<'\n';

    for(int i=1;i<=nrs;i++)
    {
        for(int j=0;j<sol[i].size();j++)
            out<<sol[i][j]<<' ';

        out<<'\n';
    }

    return 0;
}