Pagini recente » Cod sursa (job #406398) | Cod sursa (job #861933) | Cod sursa (job #2962573) | Cod sursa (job #1196265) | Cod sursa (job #1257761)
#include <fstream>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;
ifstream is("trajan.in");
ofstream os("tarjan.out");
void Write();
void Trajan( 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);
}
os << n;
/*for ( int i = 1; i <= n; i++ )
if ( index[i] == INF )
Trajan( i );
Write();*/
is.close();
os.close();
return 0;
}
void Write()
{
os << sol.size();
for ( int i = 0; i <= sol.size(); i++ )
{
os << '\n';
for ( int j = 0; j <= sol[i].size(); j++ )
os << sol[i][j] << ' ';
}
}
void Trajan( int k )
{
index[k] = L[k] = ++idx;
Q.push(k);
instack[k] = true;
for ( const auto& vecin : G[k] )
{
if ( index[y] == INF )
{
Trajan(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] )
{
aux.clear();
do
{
node = Q.top();
Q.pop();
aux.push_back(node);
instack[node] = false;
} while( node != x );
sol.push_back(aux);
}
}