Pagini recente » Cod sursa (job #983023) | Cod sursa (job #2661223) | Cod sursa (job #1500256) | Cod sursa (job #887173) | Cod sursa (job #2352905)
#include <bits/stdc++.h>
#define MAXN 100005
int N, M, CTCSize;
std::vector <int> CTC[MAXN];
std::vector <int> ADC[MAXN];
inline void AddEdge(int X, int Y) {
ADC[X].push_back(Y);
}
std::stack <int> S;
bool InStack[MAXN];
int Time, Discovery[MAXN], Lowlink[MAXN];
void Tarjan(int Vertex) {
Discovery[Vertex] = Lowlink[Vertex] = ++Time;
S.push(Vertex);
InStack[Vertex] = 1;
for (auto Edge:ADC[Vertex])
if (!Discovery[Edge])
Tarjan(Edge),
Lowlink[Vertex] = std::min(Lowlink[Vertex], Lowlink[Edge]);
else if (InStack[Edge])
Lowlink[Vertex] = std::min(Lowlink[Vertex], Lowlink[Edge]);
if (Discovery[Vertex] == Lowlink[Vertex]) {
int Top;
++ CTCSize;
do {
Top = S.top();
S.pop();
InStack[Top] = 0;
CTC[CTCSize].push_back(Top);
} while (Top != Vertex);
std::sort(CTC[CTCSize].begin(), CTC[CTCSize].end());
}
}
std::ifstream In ("ctc.in");
std::ofstream Out("ctc.out");
void Citire() {
In >> N >> M;
for (int i=1, X, Y; i<=M; ++i)
In >> X >> Y, AddEdge(X, Y);
}
void Rezolvare() {
for (int i=1; i<=N; ++i)
if (!Discovery[i])
Tarjan(i);
Out << CTCSize << '\n';
for (int i=1; i<=CTCSize; ++i, Out << '\n')
for (auto Vertex:CTC[i])
Out << Vertex << ' ' ;
}
int main()
{
Citire();
Rezolvare();
return 0;
}