Pagini recente » Cod sursa (job #748966) | Cod sursa (job #252303) | Cod sursa (job #1409409) | Cod sursa (job #1098938) | Cod sursa (job #1424186)
#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;
}