Pagini recente » Cod sursa (job #3212543) | Cod sursa (job #2784019) | Cod sursa (job #2989430) | Cod sursa (job #1119230) | Cod sursa (job #1548882)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, idx, nrc;
vector<vector<int>> G, CC;
vector<int> Index, L, C;
vector<bool> InStack;
stack<int> Stk;
void Read();
void Tarjan(int nod);
void Write();
int main()
{
Read();
for (int i = 1; i <= n; i++)
if (Index[i] == 0) Tarjan(i);
fout << nrc << '\n';
Write();
fin.close();
fout.close();
return 0;
}
void Tarjan(int nod)
{
Index[nod] = L[nod] = ++idx;
Stk.push(nod);
InStack[nod] = true;
for (const auto & x : G[nod])
if (Index[x] == 0)
{
Tarjan(x);
L[nod] = min(L[nod], L[x]);
}
else if (InStack[x])
L[nod] = min(L[nod], Index[x]);
if (Index[nod] == L[nod])
{
nrc++;
C.clear();
int nod2;
do
{
C.push_back(nod2 = Stk.top());
Stk.pop();
InStack[nod2] = false;
} while ( nod2 != nod );
CC.push_back(C);
}
}
void Write()
{
for (const auto & c : CC)
{
for (const auto & x : c)
fout << x << ' ';
fout << '\n';
}
}
void Read()
{
fin >> n >> m;
G = vector<vector<int>>(n + 1);
Index = L = vector<int>(n + 1);
InStack = vector<bool>(n + 1);
for (int i = 1, x, y; i <= m; i++)
{
fin >> x >> y;
G[x].push_back(y);
}
}