Pagini recente » Cod sursa (job #1737749) | Cod sursa (job #506484) | Cod sursa (job #1268252) | Cod sursa (job #1933860) | Cod sursa (job #2426247)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
std::ifstream fin ("ctc.in");
std::ofstream fout ("ctc.out");
using VI = std::vector<int>;
using VVI = std::vector<VI>;
using VB = std::vector<bool>;
int n, m;
int index;
VI sc, idx, lowLink;
VB inStack;
VVI G, sol;
std::stack<int> stk;
void Read();
void Tarjan(int i);
void Solve();
void Write();
int main()
{
Read();
Solve();
Write();
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> n >> m;
G = VVI(n + 1);
int x, y;
for (int i = 0; i < m; ++i)
{
fin >> x >> y;
G[x - 1].push_back(y - 1);
}
}
void Tarjan(int i)
{
idx[i] = lowLink[i] = index;
index++;
stk.push(i);
inStack[i] = true;
for (const auto& x : G[i])
{
if (idx[x] == -1)
{
Tarjan(x);
lowLink[i] = std::min(lowLink[i], lowLink[x]);
}
else if (inStack[i])
lowLink[i] = std::min(lowLink[i], lowLink[x]);
}
if (idx[i] == lowLink[i])
{
sc.clear();
int node = 0;
do
{
node = stk.top();
sc.push_back(node);
stk.pop();
inStack[node] = false;
} while(i != node);
sol.push_back(sc);
}
}
void Solve()
{
idx = VI(n + 1, -1);
lowLink = VI(n + 1);
inStack = VB(n + 1);
for (int i = 0; i < n; ++i)
if (idx[i] == -1)
Tarjan(i);
}
void Write()
{
fout << sol.size() << '\n';
for (int i = 0; i < sol.size(); ++i)
{
for (int j = 0; j < sol[i].size(); ++j)
fout << sol[i][j] + 1 << " ";
fout << "\n";
}
}