Pagini recente » Cod sursa (job #1789966) | Monitorul de evaluare | Cod sursa (job #2020844) | Cod sursa (job #2393886) | Cod sursa (job #2331146)
#include <stdio.h>
#include <string.h>
using namespace std;
#define NMAX 100005
FILE * f = fopen("ctc.in", "r");
FILE * g = fopen("ctc.out", "w");
int n, m, i, k, nrctc, viz[NMAX], st[NMAX];
struct nod {
int inf;
nod* urm;
} *l[NMAX], *lt[NMAX], *sol[NMAX];
void adaug_nod(nod* &l, int x) {
nod* p = new nod;
p->inf = x;
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);
adaug_nod(lt[y], x);
}
}
void df1(int i) {
nod *c;
viz[i] = 1;
for(c = l[i]; c != NULL; c = c->urm)
if (!viz[c->inf]) df1(c->inf);
st[++k]=i;
}
void df2(int i) {
nod *c;
viz[i]=1;
adaug_nod(sol[nrctc], i);
for(c=lt[i]; c != NULL; c=c->urm)
if (!viz[c->inf]) df2(c->inf);
}
void afisare() {
fprintf(g, "%d\n", nrctc);
for(int i = 1; i <= nrctc; i++) {
for(nod* p = sol[i]; p != NULL; p = p->urm) fprintf(g, "%d ", p->inf);
fprintf(g, "\n");
}
}
int main() {
citire();
for(i = 1; i <= n; i++)
if (!viz[i]) df1(i);
memset (viz, 0, sizeof(viz));
for(i = n; i >= 1; i--)
if (!viz[st[i]]) {
nrctc++; df2(st[i]);
}
afisare();
fclose(f); fclose(g);
return 0;
}