Pagini recente » Cod sursa (job #516506) | Cod sursa (job #614148) | Cod sursa (job #33198) | Cod sursa (job #283240) | Cod sursa (job #3284246)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
VVI G;
VVI ctc;
stack<int> stk;
VI vtemp;
VI tin, tout;
VB inStack;
int timer = 0;
int n, m;
void DFSTarjan(int x);
int main()
{
fin >> n >> m;
G = VVI(n + 1);
tin = tout = VI(n + 1);
inStack = VB(n + 1);
int x, y;
for (int i = 1; i <= m; ++i)
{
fin >> x >> y;
G[x].emplace_back(y);
}
for (int i = 1; i <= n; ++i)
if (!tin[i])
DFSTarjan(i);
fout << ctc.size() << '\n';
for (auto i : ctc)
{
for (auto j : i)
fout << j << ' ';
fout << '\n';
}
}
void DFSTarjan(int x)
{
tin[x] = tout[x] = ++timer;
inStack[x] = true;
stk.emplace(x);
for (auto& y : G[x])
if (!tin[y])
{
DFSTarjan(y);
tout[x] = min(tout[x], tout[y]);
}
else
if (inStack[y])
tout[x] = min(tout[y], tout[x]);
if (tout[x] == tin[x])
{
int y;
vtemp.clear();
while (true)
{
y = stk.top();
stk.pop();
vtemp.emplace_back(y);
inStack[y] = false;
if (tin[y] == tout[x])
break;
}
ctc.emplace_back(vtemp);
}
}