Pagini recente » Cod sursa (job #268911) | Cod sursa (job #623449) | Cod sursa (job #2132172) | Cod sursa (job #3201500) | Cod sursa (job #1255028)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream is("ctc.in");
ofstream os("ctc.out");
#define INF 0x3f3f3f3f
vector<vector<int>> G, sol;
vector<int> index, L, aux;
vector<bool> instack;
int n, m, x, y, ind;
stack<int> S;
void Trajan( int k );
int main()
{
is >> n >> m;
G.resize(n+1);
index = vector<int>(n+1, INF);
L = vector<int>(n+1);
instack = vector<bool>(n+1);
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 )
Trajan(i);
os << sol.size() << "\n";
for (const auto& c : sol)
{
for (const auto& x : c)
os << x << ' ';
os << '\n';
}
is.close();
os.close();
return 0;
}
void Trajan( int k )
{
index[k] = L[k] = ind++;
S.push(k);
instack[k] = true;
for ( const auto& y : G[k] )
if ( index[y] == INF )
{
Trajan(y);
L[k] = min(L[y], L[k] );
}
else
if ( instack[k] )
L[k] = min(L[y], L[k] );
if ( L[k] == index[k] )
{
aux.clear();
int k2;
while( true )
{
aux.push_back(k2 = S.top());
S.pop();
instack[k] = false;
if ( k2 == k )
break;
}
sol.push_back(aux);
}
}