Pagini recente » Cod sursa (job #1123929) | Cod sursa (job #2873168) | Cod sursa (job #2845937) | Cod sursa (job #2101830) | Cod sursa (job #2298346)
#include <bits/stdc++.h>
#define MAXN 200005
int N, M;
std::vector <int> ADC[MAXN];
inline void AddEdge(int x, int y) {
ADC[x].push_back(y);
}
int Disc[MAXN], Low[MAXN],
Pasi;
bool Seen[MAXN];
std::stack <int> Stack;
int NCTC;
std::vector <int> CTC[MAXN];
void Tarjan(int Vertex) {
Disc[Vertex] = Low[Vertex] = ++Pasi;
Stack.push(Vertex);
Seen[Vertex] = 1;
for (auto Vecin:ADC[Vertex]) {
if (!Disc[Vecin])
Tarjan(Vecin),
Low[Vertex] = std::min(Low[Vertex], Low[Vecin]);
if (Seen[Vecin])
Low[Vertex] = std::min(Low[Vertex], Low[Vecin]);
}
if (Disc[Vertex] == Low[Vertex]) {
CTC[NCTC].push_back(Vertex);
int Top;
do {
Top = Stack.top();
Stack.pop();
Seen[Top] = 0;
CTC[NCTC].push_back(Top));
} while (Top != Vertex);
++NCTC;
}
}
std::ifstream In("ctc.in");
std::ofstream Out("ctc.out");
void Citire() {
In >> N >> M;
for (int i=0, x, y; i<M; ++i)
In >> x >> y, AddEdge(x, y);
}
void Rezolvare() {
for (int i=1; i<=N; ++i)
if (!Disc[i])
Tarjan(i);
Out << NCTC << '\n';
for (int i=0, j; i<NCTC; ++i, Out << '\n')
for (j=0; j<CTC[i].size(); ++j)
Out << CTC[i][j] << ' ' ;
}
int main()
{
Citire();
Rezolvare();
return 0;
}