Pagini recente » Cod sursa (job #1393811) | Cod sursa (job #765740) | Cod sursa (job #363179) | Cod sursa (job #792702) | Cod sursa (job #1831955)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define DIM 100005
vector <vector <int> > G, Rez;
int tmp = 1, N, M, x, y;
int Timp[DIM], Best[DIM], viz[DIM], St[DIM], eSt[DIM];
void DF(int nod);
int main() {
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d\n", &N, &M);
G.resize(N + 2);
for(int i = 1; i <= M; ++i) {
scanf("%d %d\n", &x, &y);
G[x].push_back(y);
}
for(int i = 1; i <= N; ++i) {
if(!viz[i]) {
DF(i);
}
}
cout << Rez.size() << '\n';
for(unsigned int c = 0; c < Rez.size(); ++c) {
for(unsigned int z = 0; z < Rez[c].size(); ++z) {
cout << Rez[c][z] << ' ';
}
cout << '\n';
}
return 0;
}
void DF(int nod) {
viz[nod] = 1;
St[++St[0]] = nod;
eSt[nod] = 1;
Timp[nod] = tmp;
Best[nod] = tmp++;
for(unsigned int z = 0; z < G[nod].size(); ++z) {
if(!viz[G[nod][z]]) {
DF(G[nod][z]);
Best[nod] = min(Best[nod], Best[G[nod][z]]);
}
else {
if(eSt[G[nod][z]] == 1) {
Best[nod] = min(Best[nod], Best[G[nod][z]]);
}
}
}
if(Best[nod] == Timp[nod]) {
vector <int> x;
while(St[St[0]] != nod) {
x.push_back(St[St[0]]);
eSt[St[St[0]]] = 0;
--St[0];
}
x.push_back(nod);
Rez.push_back(x);
eSt[nod] = 0;
--St[0];
}
}