Pagini recente » Cod sursa (job #2183057) | Cod sursa (job #2219713) | Cod sursa (job #2980917) | Cod sursa (job #1162138) | Cod sursa (job #2331084)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define NMAX 100005
FILE * f = fopen("ctc.in", "r");
FILE * g = fopen("ctc.out", "w");
int n, m, index, ssize, nrcct, s[NMAX], idx[NMAX], lowlink[NMAX], onstack[NMAX], cct[NMAX];
struct nod{
int inf;
nod* urm;
} *l[NMAX], *sol[NMAX];
void adaug_nod(nod* &l, int y) {
nod* p = new nod;
p->inf = y;
p->urm = l;
l = p;
}
void citire() {
int x, y;
fscanf(f, "%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
fscanf(f, "%d%d", &x, &y);
adaug_nod(l[x], y);
}
}
void tarjan(int v) {
int x;
s[++ssize] = v; onstack[v] = 1;
idx[v] = lowlink[v] = ++index;
for(nod* p = l[v]; p != NULL; p = p->urm) {
int u = p->inf;
if(!idx[u]) {
tarjan(u);
lowlink[v] = min(lowlink[v], lowlink[u]);
}
else if(onstack[u]) lowlink[v] = min(lowlink[v], lowlink[u]);
}
if(idx[v] == lowlink[v]) {
nrcct++;
do {
x = s[ssize];
adaug_nod(sol[nrcct], x);
onstack[x] = 0; ssize--;
} while(x != v);
}
}
void afisare() {
fprintf(g, "%d\n", nrcct);
for(int i = 1; i <= nrcct; i++) {
for(nod* p = sol[i]; p != NULL; p = p->urm) fprintf(g, "%d ", p->inf);
fprintf(g, "\n");
}
}
int main() {
citire();
for(int i = 1; i <= n; i++)
if(!idx[i]) tarjan(i);
afisare();
fclose(f); fclose(g);
return 0;
}