Pagini recente » Cod sursa (job #2683168) | Cod sursa (job #1478182) | Cod sursa (job #1195003) | Cod sursa (job #1295292) | Cod sursa (job #1414294)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> V[100002];
int D[100002], minD[100002];
int ST[100002];
bool inST[100002];
vector<vector<int> > comp;
void Tarjan(int x)
{
D[x] = ++D[0];
minD[x] = D[x];
ST[++ST[0]] = x;
inST[x] = true;
for (auto nod : V[x])
if (!D[nod])
{
Tarjan(nod);
minD[x] = min(minD[x], minD[nod]);
}
else if (inST[nod])
minD[x] = min(minD[x], minD[nod]);
if (minD[x] == D[x])
{
comp.push_back(vector<int>());
while (true)
{
comp.back().push_back(ST[0]);
inST[ST[0]] = false;
--ST[0];
if (ST[ST[0] + 1] == x) break;
}
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> N >> M;
for (int i = 1, nod1, nod2; i <= M; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
}
for (int i = 1; i <= N; ++i)
if (!D[i])
Tarjan(i);
fout << comp.size() << '\n';
for (auto v : comp)
{
for (auto nod : v)
fout << nod << ' ';
fout << '\n';
}
fin.close();
fout.close();
}