Pagini recente » Cod sursa (job #804340) | Cod sursa (job #367979) | Cod sursa (job #129548) | Statistici pohoatza (pohoatza) | Cod sursa (job #2240149)
#include <bits/stdc++.h>
#define MaxN 100005
#define MaxM 200005
std::ifstream InFile("ctc.in");
std::ofstream OutFile("ctc.out");
int N, M;
std::list <int> Arc[MaxN], ArcT[MaxN];
std::vector <int> CTC[MaxN];
std::stack <int> OrderStack;
int CTCCount;
bool Seen[MaxN];
void DFS1(int Node) {
Seen[Node] = 1;
for (auto Vec:Arc[Node])
if(!Seen[Vec])
DFS1(Vec);
OrderStack.push(Node);
}
void DFS2(int Node) {
Seen[Node] = 1;
for (auto Vec:ArcT[Node])
if(!Seen[Vec])
DFS2(Vec);
CTC[CTCCount].push_back(Node);
}
void Citire() {
InFile >> N >> M;
for (int i=0, x, y; i<M; i++)
InFile >> x >> y,
Arc[x].push_back(y),
ArcT[y].push_back(x);
}
void Rezolvare() {
for (int i=0, j; i<N; i++)
if(!Seen[i+1])
DFS1(i+1);
for (int i=0, j; i<N; i++)
Seen[i+1] = 0;
int StackTop;
while(!OrderStack.empty()) {
StackTop = OrderStack.top();
OrderStack.pop();
if(!Seen[StackTop])
DFS2(StackTop),
CTCCount++;
}
OutFile << CTCCount << '\n';
for (int i=0, j; i<CTCCount; i++) {
for (j=0; j<CTC[i].size(); j++)
OutFile << CTC[i][j] << ' ' ;
OutFile << '\n';
}
}
int main()
{
Citire();
Rezolvare();
return 0;
}