Pagini recente » Cod sursa (job #3280803) | Istoria paginii runda/oji_in_iulie_lol | Cod sursa (job #838551)
Cod sursa(job #838551)
#include <cstdio>
#define MAXN 100001
using namespace std;
struct nod {int inf; nod* urm;};
int n, m, mrk = 0;
nod* v[MAXN];
nod* vt[MAXN];
int mark[MAXN];
void push (int x, int y) {
nod* p;
p = new nod;
p->inf = y;
p->urm = v[x];
v[x] = p;
p = new nod;
p->inf = x;
p->urm = vt[y];
vt[y] = p;
}
void read () {
freopen ("ctc.in", "r", stdin);
scanf ("%d%d", &n, &m);
int i, x, y;
for (i=1; i<=m; ++i) {
scanf ("%d%d", &x, &y);
push (x, y);
}
fclose (stdin);
}
int nr, postord[MAXN];
bool viz[MAXN];
void DFS (int i) {
viz[i] = 1;
nod* p;
p = v[i];
while (p) {
if (!viz[p->inf])
DFS (p->inf);
p = p->urm;
}
postord[++nr] = i;
}
void DFST (int i) {
viz[i] = 0;
mark[i] = mrk;
nod* p;
p = vt[i];
while (p) {
if (viz[p->inf])
DFST (p->inf);
p = p->urm;
}
}
void solve () {
int i;
for (i=1; i<=n; ++i)
if (!viz[i])
DFS(i);
for (i=n; i>0; --i)
if (viz[postord[i]]) {
++mrk;
DFST (postord[i]);
}
}
void write () {
freopen ("ctc.out", "w", stdout);
printf ("%d\n", mrk);
int i, j;
for (i=1; i<=mrk; ++i) {
for (j=1; j<=n; ++j)
if (mark[j] == i)
printf ("%d ", j);
printf ("\n");
}
fclose (stdout);
}
int main () {
read ();
solve ();
write ();
return 0;
}