Pagini recente » Cod sursa (job #1510526) | Cod sursa (job #3124274) | Cod sursa (job #704916) | Cod sursa (job #2517174) | Cod sursa (job #1451627)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <sstream>
#define MIN(a,b) ((a)<(b))?(a):(b)
const char IN[] = "ctc.in", OUT[] = "ctc.out";
const int NMAX = 100001;
enum {WHITE, GREY, BLACK};
using namespace std;
list<int> G[NMAX];
int N, M;
inline void read_data() {
freopen(IN, "r", stdin);
scanf("%d %d", &N, &M);
for (int i = 0; i < M; ++i) {
int src, dst;
scanf("%d %d", &src, &dst);
G[src].push_back(dst);
}
fclose(stdin);
}
int i = 0;
int lowlink[NMAX], index[NMAX];
stack<int> S;
bool inS[NMAX];
int ctcCount;
ostringstream sout;
void Tarjan(int node) {
index[node] = lowlink[node] = ++i;
S.push(node);
inS[node] = true;
for (const int n : G[node]) {
if (index[n] == 0 || inS[n]) {
if (!index[n]) Tarjan(n);
lowlink[node] = MIN(lowlink[node], lowlink[n]);
}
}
if (index[node] == lowlink[node]) {
++ctcCount;
int v;
do {
v = S.top(); S.pop();
sout << v << " ";
} while (v != node);
sout << endl;
}
}
int main() {
read_data();
for (int node = 1; node <= N; ++node) {
if (!index[node]) Tarjan(node);
}
fprintf(fopen(OUT, "w"), "%d\n%s", ctcCount, sout.str().c_str());
return 0;
}