Pagini recente » Cod sursa (job #1541972) | Cod sursa (job #1563621) | Cod sursa (job #2313902) | Cod sursa (job #733487) | Cod sursa (job #2240121)
#include <bits/stdc++.h>
#define MaxN 100005
#define MaxM 200005
#define Finished 2
#define Value1 1
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];
int CTCCount;
int State[MaxN];
void DFS1(int Node) {
State[Node] = Value1;
for (auto Vec:Arc[Node])
if(State[Vec] == 0)
DFS1(Vec);
}
void DFS2(int Node) {
State[Node] = Finished;
CTC[CTCCount].push_back(Node);
for (auto Vec:ArcT[Node])
if(State[Vec] == Value1)
DFS2(Vec);
}
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(State[i+1] != Finished) {
DFS1(i+1);
DFS2(i+1);
CTCCount++;
for (j=0; j<N; j++)
if(State[j+1] != Finished)
State[j+1] = 0;
}
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;
}