Pagini recente » Cod sursa (job #1487933) | Cod sursa (job #1987429) | Cod sursa (job #2761546) | Cod sursa (job #1885932) | Cod sursa (job #1897755)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
const int Inf = 0x3f3f3f3f;
int n, m, a, b;
int idx;
vector<vector<int> > G, sol;
vector<int> index, L, c;
vector<bool> inStack;
stack<int> st;
void Read()
{
int x,y;
fi >> n >> m;
G.resize(n + 1);
index.resize(n + 1,Inf);
L.resize(n + 1);
inStack.resize(n + 1);
for ( int i = 1; i <= m; ++i )
{
fi >> x >> y;
G[x].push_back(y);
}
}
void Write()
{
fo << sol.size() << "\n";
for ( size_t i = 0; i < sol.size(); ++i,fo<<'\n' )
for ( size_t j = 0; j < sol[i].size(); ++j )
fo << sol[i][j] << " ";
}
void Tarjan(int x)
{
index[x] = L[x] = idx++;
st.push(x);
inStack[x] = true;
for ( const int & y : G[x] )
if ( index[y] == Inf ) // muchie de arbore
{ Tarjan(y);
L[x] = min(L[x], L[y]);
}
else if( inStack[y] ) //muchie de intoarcere
L[x] = min(L[x], index[y]);
if ( index[x] == L[x] ) // am gasit o noua comp.tare conexa
{
c.clear();
int y;
do
{ y=st.top();
st.pop();
inStack[y] = false;
c.push_back(y);
} while ( y != x );
sol.push_back(c);
}
}
int main()
{
Read();
for ( int i = 1; i <= n; ++i )
if ( index[i] == Inf ) Tarjan(i);
Write();
return 0;
}