Pagini recente » Cod sursa (job #357778) | Cod sursa (job #12241) | Cod sursa (job #2033927) | Cod sursa (job #102144) | Cod sursa (job #981727)
Cod sursa(job #981727)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define Nmax 100002
vector<bool> visit(Nmax);
vector<bool> in_stack(Nmax);
vector<int> low(Nmax);
vector<int> ind(Nmax);
stack<int> ST;
vector<int> S[Nmax];
vector<int> G[Nmax];
int N, M, NR, indecs;
void read()
{
ifstream f("ctc.in");
f >> N >> M;
for ( int i = 1, a, b; i <= M; ++i )
{
f >> a >> b;
G[a].push_back( b );
}
f.close();
}
void Tarjan( int node )
{
visit[node] = 1;
in_stack[node] = 1;
indecs++;
ind[node] = low[node] = indecs;
ST.push( node );
for ( unsigned i = 0; i < G[node].size(); ++i )
{
if ( !visit[ G[node][i] ] )
{
Tarjan( G[node][i] );
low[node] = min( low[node], low[ G[node][i] ] );
}
else
if ( in_stack[ G[node][i] ] )
{
low[node] = min( low[node], low[ G[node][i] ] );
}
}
if ( low[node] == ind[node] )
{
NR++;
while( ST.top() != node )
{
in_stack[ ST.top() ] = 0;
S[NR].push_back( ST.top() );
ST.pop();
}
ST.pop();
in_stack[node] = 0;
S[NR].push_back( node );
}
}
void solve()
{
for ( int i = 1; i <= N; ++i )
if ( !visit[i] )
Tarjan( i );
}
void print()
{
ofstream g("ctc.out");
g << NR << "\n";
for ( int i = 1; i <= NR; ++i )
{
for ( unsigned j = 0; j < S[i].size(); ++j )
g << S[i][j] << " ";
g << "\n";
}
g.close();
}
int main()
{
read();
solve();
print();
return 0;
}