Pagini recente » Cod sursa (job #3251397) | Cod sursa (job #2583615) | Cod sursa (job #538688) | Cod sursa (job #2670453) | Cod sursa (job #253323)
Cod sursa(job #253323)
#include <cstdio>
#include <cstring>
using namespace std;
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define MAX_N 100005
typedef struct NOD
{
int nod;
NOD *next;
};
NOD *G[MAX_N];
NOD *Gt[MAX_N];
unsigned char V[MAX_N];
int P[MAX_N];
int cnt;
int res;
int N, M;
void readdata ()
{
int i, a, b;
scanf ("%d %d", &N, &M);
for (i = 1; i <= M; ++i)
{
scanf ("%d %d", &a, &b);
NOD *q = new (NOD);
q->nod = b, q->next = G[a], G[a] = q;
NOD *p = new (NOD);
p->nod = a, p->next = Gt[b], Gt[b] = p;
}
}
void DFSt (int nod)
{
V[nod] = 0;
for (NOD *q = Gt[nod]; q != NULL; q = q->next)
if (V[q->nod]) DFSt (q->nod);
}
void DFSta (int nod)
{
V[nod] = 0;
printf ("%d ", nod);
for (NOD *q = Gt[nod]; q != NULL; q = q->next)
if (V[q->nod]) DFSta (q->nod);
}
void DFS (int nod)
{
V[nod] = 1;
for (NOD *q = G[nod]; q != NULL; q = q->next)
if (!V[q->nod]) DFS (q->nod);
P[++cnt] = nod;
}
void solve ()
{
int i;
for (i = 1; i <= N; ++i)
if (!V[i]) DFS (i);
for (i = N; i; --i)
if (V[P[i]])
{
++res;
DFSt(P[i]);
}
printf ("%d\n", res);
memset (V, 1, sizeof (V));
for (i = N; i; --i)
if (V[P[i]])
{
++res;
DFSta(P[i]);
printf ("\n");
}
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
readdata ();
solve ();
return 0;
}