Cod sursa(job #2246408)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 27 septembrie 2018 08:40:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.13 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#define NMAX 100001
#define mp make_pair
#define pb push_back
#define nod1 first
#define nod2 second

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int N, M, i, j, x, y;
int Low[NMAX]; //tin pentru fiecare nod nivelul minim pe care poate sa ajunga din arborele DF - vezi puncte articulatie
int Level[NMAX]; //tin pentru fiecare nod nivelul atins in arborele DF
int T[NMAX]; //tin pentru fiecare nod tatal sau din arborele DF
int Written[NMAX]; //vector folosit la afisarea componentelor - finalul sursei
vector< int > G[NMAX]; //listele de adiacenta
vector< vector < int > > Comp; //memoreaza toate componentele biconexe sub forma de vectori
stack< pair< int, int > > Muchii; //stiva in care retin muchiile in parcurgerea DF
bool USED[NMAX]; //verific pentru fiecare nod daca a fost sau nu atins in parcurgerea DF

inline void MemComp( int X, int Y )
{
    vector< int > C;
    pair< int, int > Mct, M1 = mp( X, Y ), M2 = mp( Y, X );

    do
    {
        Mct = Muchii.top(); //iau o muchie din stiva
        C.pb( Mct.nod1 ); //ii memorez nodurile in vectorul pentru componenta biconexa noua
        C.pb( Mct.nod2 );
        Muchii.pop(); //scot muchia din stiva
    }
    while( Mct != M1 );//&& Mct != M2 ); //pana ajung la muchia (*it - NOD)

    Comp.pb( C ); //inserez componenta biconexa nou gasita in vectorul de componente
}

inline void DF( int NOD )
{
    USED[NOD] = true;
    Low[NOD] = Level[NOD];

    for( vector< int >::iterator it = G[NOD].begin(); it != G[NOD].end(); it++ )
    {
        int curent=*it;
        if( *it != T[NOD] && Level[NOD] > Level[*it] )
            Muchii.push( mp( NOD, *it ) ); //introduc muchia in stiva

        if( !USED[*it] )
        {
            Level[*it] = Level[NOD] + 1;
            T[*it] = NOD;

            DF( *it );

            if( Low[NOD] > Low[*it] )
                Low[NOD] = Low[*it];

            if( Low[*it] >= Level[NOD] )
                MemComp( NOD, *it ); //am gasit un punct de articulatie (NOD) deoarece *it (un fiu de-al nodului) nu ajunge mai sus de el in arborele DF
        }
        else if( *it != T[NOD] && Low[NOD] > Level[*it] )
            Low[NOD] = Level[*it];
    }
}

int main()
{


    fin >> N >> M;
    while( M-- )
    {
        fin >> x >> y;
        G[x].pb( y );
        G[y].pb( x );
    }

    memset( USED, false, sizeof(USED) );

    Level[1] = 1;
    DF( 1 );

    fout << Comp.size() << '\n';
    for( i=0; i<Comp.size(); i++ ) //pentru fiecare componenta biconexa in parte
    {
        for( j=0; j<Comp[i].size(); j++ )
            Written[Comp[i][j]] = i; //marchez nodurile din componenta biconexa curenta pentru afisare

        for( j=0; j<Comp[i].size(); j++ )
            if( Written[Comp[i][j]] == i )
            {
                fout << Comp[i][j] << ' '; //afisez nodul din componenta biconexa
                Written[Comp[i][j]] = -1; //il marchez cu -1 ca sa nu il mai afisez a doua oara
            }
        fout << '\n';
    }

    return 0;
}