Pagini recente » Cod sursa (job #2477943) | Cod sursa (job #294547) | Istoria paginii runda/sim10_1/clasament | Cod sursa (job #1321853) | Cod sursa (job #2240166)
#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];
std::vector <int> CTC[MaxN];
int CTCCount;
int Ord[MaxN], Low[MaxN];
bool IsStacked[MaxN];
std::stack <int> NodeStack;
int Pasi;
void DFSTarjan(int Node) {
Ord[Node] = Low[Node] = ++Pasi;
NodeStack.push(Node);
IsStacked[Node] = 1;
for (auto Vec:Arc[Node]) {
if(Ord[Vec]) {
if(IsStacked[Vec]);
Low[Node] = std::min(Low[Node], Ord[Vec]);
}
else {
DFSTarjan(Vec);
Low[Node] = std::min(Low[Node], Low[Vec]);
}
}
if(Ord[Node] == Low[Node]) {
int StackTop;
do {
StackTop = NodeStack.top();
NodeStack.pop();
IsStacked[StackTop] = 0;
CTC[CTCCount].push_back(StackTop);
} while(StackTop != Node);
CTCCount++;
}
}
void Citire() {
InFile >> N >> M;
for (int i=0, x, y; i<M; i++)
InFile >> x >> y,
Arc[x].push_back(y);
}
void Rezolvare() {
for (int i=0, j; i<N; i++)
if(!Ord[i+1])
DFSTarjan(i+1);
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;
}