Cod sursa(job #1424186)

Utilizator CalinCojoFMI Cojocaru Calin George CalinCojo Data 23 aprilie 2015 18:10:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>

#define N 100002
using namespace std;

bitset <1> viz [ N ] , in_stack [ N ] ;
stack < unsigned int > stiva;
vector <unsigned int > lista [ N ] , sol ;
int indx [ N ] , low_indx [ N ] , index , ctc  ;


int minim ( int x, int y){
    if (x<=y) return x;
    return y;
}

void tarjan ( unsigned int node) {

    viz [ node ] = 1;
    in_stack [ node ] =1;
    stiva.push ( node );
    index++;
    indx [ node ] = index;
    low_indx [ node ] = index ;

    unsigned int i;
    for ( i = 0 ; i < lista [ node].size() ; i++ )
    {
        if ( viz  [ lista[ node ] [ i ] ] == 0 )
            {
                tarjan( lista [ node ] [ i ]  ) ;
                low_indx [ node ] = minim ( low_indx [ node ] , low_indx [ lista [ node ] [ i ] ] ) ;
            }
        else if ( in_stack [ lista [ node ] [ i ] ] == 1 )
            {
                low_indx [ node ] = minim ( low_indx [ node ] , low_indx [ lista [ node ] [ i ] ] ) ;
            }
    }

    if( indx [ node ] == low_indx [ node ] ) // am dat peste o ctc
    {
        ctc++;
        int nd ;
        do{
            nd = stiva.top() ;
            sol.push_back(nd) ;
            in_stack [ nd ] = 0 ;
            stiva.pop();
        } while ( node != nd);
        sol.push_back(-1);
    }


}



int main()
{
    unsigned int n , m,x,y , i;
    ifstream f( "ctc.in" , ios::in) ;
    ofstream g( "ctc.out", ios::out) ;
    f>>n>>m;

    while(m){
        m--;
        f>>x>>y;
        lista [ x ].push_back( y );
    }

    for ( i = 1; i <= n; i++)
        if ( viz [ i ] == 0 )
            tarjan ( i ) ;

    g<<ctc<<"\n";
    for ( i = 0 ; i < sol.size() ; i++)
        if ( sol [ i ] == -1)
            g<<"\n";
        else
            g<<sol [ i ]<<"  ";

    return 0;
}