Pagini recente » Cod sursa (job #1599670) | Cod sursa (job #683187) | Cod sursa (job #1505371) | Cod sursa (job #554173) | Cod sursa (job #954823)
Cod sursa(job #954823)
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int MAXN = 100010;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> G[MAXN];
vector <vector <int>> CTC;
int dfsIdx[MAXN], lowIdx[MAXN], N, idx;
bool inStack[MAXN];
stack <int> vStack;
void DFS (int v)
{
vStack.push (v);
inStack[v] = true;
dfsIdx[v] = lowIdx[v] = ++idx;
for (auto &n : G[v])
if (!dfsIdx[n])
{
DFS (n);
lowIdx[v] = min (lowIdx[v], lowIdx[n]);
}
else if (inStack[n])
lowIdx[v] = min (lowIdx[v], lowIdx[n]);
if (lowIdx[v] == dfsIdx[v])
{
int x;
CTC.push_back (vector <int>());
do {
x = vStack.top();
vStack.pop();
inStack[x] = false;
CTC.back().push_back (x);
} while (x != v);
}
}
int main()
{
int m;
for (fin >> N >> m; m; --m)
{
int x, y;
fin >> x >> y;
G[x].push_back (y);
}
for (int v = 1; v <= N; ++v)
if (!dfsIdx[v])
DFS (v);
fout << CTC.size() << '\n';
for (auto &ctc : CTC)
{
for (auto &v : ctc)
fout << v << ' ';
fout << '\n';
}
return EXIT_SUCCESS;
}