Pagini recente » Cod sursa (job #898316) | Cod sursa (job #139428) | Cod sursa (job #128407) | Cod sursa (job #294801) | Cod sursa (job #949250)
Cod sursa(job #949250)
#include <vector>
#include <fstream>
#include <cstdlib>
using namespace std;
const int NMAX = 100011;
int idx, countStc;
bool isInStack[NMAX];
int dfsIdx[NMAX], lowIdx[NMAX];
vector<int> S;
vector<int> G[NMAX], Stc[NMAX];
inline void DFS(int x)
{
S.push_back(x);
isInStack[x] = true;
dfsIdx[x] = lowIdx[x] = ++idx;
for(auto& y : G[x])
{
if(!dfsIdx[y])
{
DFS(y);
lowIdx[x] = min(lowIdx[x], lowIdx[y]);
}
else if(isInStack[y])
{
lowIdx[x] = min(lowIdx[x], lowIdx[y]);
}
}
if(dfsIdx[x] == lowIdx[x])
{
int y;
do
{
Stc[countStc].push_back(y = S.back()); S.pop_back();
isInStack[y] = false;
}while(x != y);
++countStc;
}
}
int main()
{
int N, M, x, y;
ifstream in("ctc.in");
ofstream out("ctc.out");
for(in >> N >> M; M; --M)
{
in >> x >> y;
G[x].push_back(y);
}
for(x = 1; x <= N; ++x)
{
if(!dfsIdx[x])
{
DFS(x);
}
}
out << countStc << '\n';
for(x = 0; x < countStc; ++x)
{
for(auto& y : Stc[x])
{
out << y << ' ';
}
out << '\n';
}
return EXIT_SUCCESS;
}