Pagini recente » Cod sursa (job #1982685) | Cod sursa (job #1125787) | Cod sursa (job #329546) | Cod sursa (job #1900218) | Cod sursa (job #2928469)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n, m;
vector < vector < int > > g, gt, ctc; // g = listele de adiacenta, gt = listele de adiacenta pentru graful compus, ctc = componenetele tare conexe
int viz[100000]; // 0 = nu a fost vizitat niciodata, 1 = vizitat dupa primul dfs, 2 = vizitat si prin dfs-ul de pe graful transpus
stack < int > s;
void citire()
{
ifstream f( "ctc.in" );
f >> n >> m;
g.resize( n + 1 );
gt.resize( n + 1 );
for( int i = 0; i < m; ++i )
{
int x, y;
f >> x >> y;
g[x].push_back( y );
gt[y].push_back( x );
}
f.close();
}
void dfs1( int nod )
{
viz[nod] = 1;
for( int i = 0; i < g[nod].size(); ++i )
if( !viz[ g[nod][i] ] )
dfs1( g[nod][i] );
s.push( nod );
}
void dfs2( int nod )
{
viz[nod] = 2;
ctc[ ctc.size() - 1 ].push_back( nod ); // tinand cont ca adaugam o ctc noua la fiecare dfs pe graful transpus, vom introduce nodurile in noua ctc (ultima)
for( int i = 0; i < gt[nod].size(); ++i )
if( viz[ gt[nod][i] ] != 2 )
dfs2( gt[nod][i] );
}
int main()
{
citire();
for( int i = 1; i <= n; ++i )
if( !viz[i] )
dfs1( i );
while( !s.empty() )
{
if( viz[ s.top() ] == 1 )
{
vector < int > aux;
ctc.push_back( aux );
dfs2( s.top() );
}
s.pop();
}
ofstream g( "ctc.out" );
g << ctc.size() << "\n";
for( int i = 0; i < ctc.size(); ++i )
{
for( int j = 0; j < ctc[i].size(); ++j )
g << ctc[i][j] << " ";
g << "\n";
}
g.close();
return 0;
}
// Algoritmul lui Kosaraju - Complexitate O( n + m )