Pagini recente » Cod sursa (job #932705) | Cod sursa (job #2438493) | Cod sursa (job #1965672) | Cod sursa (job #2611834) | Cod sursa (job #1257762)
#include <fstream>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;
ifstream is("ctc.in");
ofstream os("ctc.out");
void Write();
void Tarjan( int k );
int idx, n, m, x, y;
vector<vector<int>> G;
vector<vector<int>> sol;
vector<int> index;
vector<int> L;
vector<int> aux;
vector<bool> instack;
stack<int> Q;
int main()
{
is >> n >> m;
G.resize(n+1);
instack = vector<bool>(n+1);
index = vector<int>(n+1);
L = vector<int>(n+1);
for ( int i = 1; i <= n; i++ )
index[i] = INF;
for ( int i = 1; i <= m; i++ )
{
is >> x >> y;
G[x].push_back(y);
}
for ( int i = 1; i <= n; i++ )
if ( index[i] == INF )
Tarjan( i );
Write();
is.close();
os.close();
return 0;
}
void Write()
{
os << sol.size() << '\n';
for (int i = 0; i < sol.size(); ++i)
{
for (int j = 0; j < sol[i].size(); ++j)
os << sol[i][j] << ' ';
os << '\n';
}
}
void Tarjan( int k )
{
index[k] = L[k] = ++idx;
Q.push(k);
instack[k] = true;
for ( const auto& y : G[k] )
{
if ( index[y] == INF )
{
Tarjan(y);
L[k] = min(L[y], L[k]);
}
else
{
if ( instack[y] )
L[k] = min(L[y], L[k] );
}
}
int node;
if ( L[k] == index[k] )
{
do
{
node = Q.top();
Q.pop();
aux.push_back(node);
instack[node] = false;
} while( node != k );
sol.push_back(aux);
aux.clear();
}
}