Pagini recente » Cod sursa (job #1565515) | Cod sursa (job #418787) | Cod sursa (job #495105) | Cod sursa (job #2946998) | Cod sursa (job #1194371)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define maxN 100005
#define PB push_back
vector <int> dGraph[maxN], tGraph[maxN], sol[maxN], Q;
bool viz[maxN];
int N, M, nrCTC;
void DFP(int nod) {
viz[nod] = true;
for(unsigned int i = 0; i < dGraph[nod].size(); ++ i) {
int nod2 = dGraph[nod][i];
if(viz[nod2]) continue;
DFP(nod2);
}
Q.PB(nod);
}
void DFM(int nod) {
viz[nod] = true;
sol[nrCTC].PB(nod);
for(unsigned int i = 0; i < tGraph[nod].size(); ++ i) {
int nod2 = tGraph[nod][i];
if(viz[nod2]) continue;
DFM(nod2);
}
}
void kosaraju() {
for(int i = 1; i <= N; ++ i) {
if(viz[i]) continue;
DFP(i);
}
for(int i = 1; i <= N; ++ i)
viz[i] = false;
for(int i = Q.size() - 1; i >= 0; -- i) {
int nod = Q[i];
if(viz[nod]) continue;
++ nrCTC;
DFM(nod);
}
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> N >> M;
while(M --) {
int x, y;
f >> x >> y;
dGraph[x].PB(y);
tGraph[y].PB(x);
}
kosaraju();
g << nrCTC << '\n';
for(int i = 1; i <= nrCTC; ++ i) {
for(unsigned int j = 0; j < sol[i].size(); ++ j)
g << sol[i][j] << " ";
g << '\n';
}
return 0;
}