Cod sursa(job #1752063)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 2 septembrie 2016 17:42:14
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <cstring>
#include <vector>
#include <stack>


using namespace std;

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

int DFN[100001], LowestAncestor[100001], NrNoduri, NrMuchii;


void PrintComp(int);
void CompBiconexe(int X, int TataX);


int x, y, NrComp;


stringstream OUT;
stack<int> Noduri;
vector<int> A[100001];

int main()
{
    f >> NrNoduri >> NrMuchii;

    for ( int i=1 ; i<=NrMuchii ; ++i )
    {
        f >> x >> y;

        A[x].push_back(y);
        A[y].push_back(x);
    }
    CompBiconexe(1, 0);

    g << NrComp << '\n';
    g << OUT.str();
}

void CompBiconexe(int X, int TataX)
{
	static int DFCOUNTER = 0;
    LowestAncestor[X] = DFN[X] = ++DFCOUNTER;

    for ( vector<int>::iterator it = A[X].begin() ; it!=A[X].end() ; ++it )
    {
        int vecin = *it;

        if ( vecin != TataX && DFN[vecin] == 0 ) //Nod nevizitat
            Noduri.push( vecin );

        if ( vecin != TataX && DFN[vecin] != 0 ) //[X, vecin] muchie de intoarcere
            LowestAncestor[X] = min(LowestAncestor[X], DFN[vecin]);


        if ( !DFN[vecin] ) //Daca vecinul nu a mai fost vizitat
        {
            CompBiconexe( vecin, X );
            LowestAncestor[X] = min(LowestAncestor[X], LowestAncestor[vecin]);

            if ( LowestAncestor[vecin] >= DFN[X] )
            {
                PrintComp(X);
                NrComp++;
            }
        }
    }
}

void PrintComp(int Last)
{
    while ( !Noduri.empty() && Noduri.top() != Last )
    {
        OUT << Noduri.top() << ' ';
        Noduri.pop();
    }

    OUT << Last << '\n';
}