Pagini recente » Cod sursa (job #10169) | Cod sursa (job #684444) | Cod sursa (job #2744043) | Cod sursa (job #606225) | Cod sursa (job #804737)
Cod sursa(job #804737)
#include <cstdio>
#define MAXN 1001
using namespace std;
struct nod { int inf; nod* next;};
int n, m, nr, c;
nod* v[MAXN];
nod* vt[MAXN];
int postord[MAXN], viz[MAXN], con[MAXN];
void init () {
for (int i=1; i<=n; ++i)
v[i] = vt[i] = NULL;
}
void v_push (int x, int y) {
nod* p;
p = new nod;
p->inf = y;
p->next = v[x];
v[x] = p;
}
void vt_push (int x, int y) {
nod* p;
p = new nod;
p->inf = y;
p->next = vt[x];
vt[x] = p;
}
void read () {
freopen ("ctc.in", "r", stdin);
scanf ("%d%d", &n, &m);
init ();
int i, x, y;
for (i=1; i<=m; ++i) {
scanf ("%d%d", &x, &y);
v_push (x, y);
vt_push (y, x);
}
}
void DFST (int x) {
viz[x] = 0;
con[x] = c;
nod* p; p = new nod;
p = vt[x];
while (p) {
if (viz[p->inf])
DFST(p->inf);
p = p->next;
}
}
void DFS (int x) {
viz[x] = 1;
nod* p; p = new nod;
p = v[x];
while (p) {
if (viz[p->inf] == 0)
DFS (p->inf);
p = p->next;
}
postord[++nr] = x;
}
void write () {
freopen ("ctc.out", "w", stdout);
int i, j;
printf ("%d\n", c);
for (i=1; i<=c; ++i) {
for (j=1; j<=n; ++j)
if (con[j] == i)
printf ("%d ", j);
printf ("\n");
}
fclose (stdout);
}
int main () {
int i;
read ();
for (i=1; i<=n; ++i)
if (viz[i] == 0) DFS(i);
for (i=n; i>0; --i)
if (viz[postord[i]]) {
++c;
DFST (postord[i]);
}
write ();
return 0;
}