Pagini recente » Cod sursa (job #2437324) | Cod sursa (job #916882) | Borderou de evaluare (job #1569113) | Cod sursa (job #2209716) | Cod sursa (job #1425109)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <sstream>
#define NMAX 100001
#define min(a,b) ((a) < (b))?(a):(b)
using namespace std;
const char IN[] = "ctc.in", OUT[] = "ctc.out";
vector<int> G[NMAX];
int lowlink[NMAX];
int index[NMAX];
int stime = 0;
int N;
bool inStack[NMAX];
int NRS = 0;
ostringstream out;
inline void readData() {
FILE *fin = freopen(IN, "r", stdin);
if (!fin) return;
int M;
scanf(" %d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int s, d;
scanf(" %d%d", &s, &d);
G[s].push_back(d);
}
fclose(stdin);
}
stack<int> S;
void tarjan(int nod) {
index[nod] = lowlink[nod] = ++stime;
S.push(nod);
inStack[nod] |= 1;
for (const int n : G[nod]) {
if (index[n] == 0) {
tarjan(n);
lowlink[nod] = min(lowlink[nod], lowlink[n]);
}
else if (inStack[n]) {
lowlink[nod] = min(lowlink[nod], lowlink[n]);
}
}
if (lowlink[nod] == index[nod]) {
//root
int u;
do {
u = S.top(); S.pop();
inStack[u] &= 0;
out << u << " ";
} while (u != nod);
NRS++;
out << endl;
}
}
int main() {
readData();
freopen(OUT, "w", stdout);
for (int i = 1; i <= N; i++)
if (index[i] == 0) tarjan(i);
printf("%d\n", NRS);
cout << out.str();
fclose(stdout);
}