Pagini recente » Cod sursa (job #2669290) | Monitorul de evaluare | Cod sursa (job #3270514) | Cod sursa (job #2114102) | Cod sursa (job #1461249)
#include <stdio.h>
#define MAXN 100000
#define MAXM 200000
int no = 0;
int nod[2 * MAXM], next[2 * MAXM], ult[MAXN];
int urm[MAXN], prim[MAXN], nr = 0;
int stiv[MAXN], dr = 0, lo[MAXN], val[MAXN];
char pest[MAXN];
inline int min2(int a, int b){
return a < b ? a : b;
}
void caut(int x){
stiv[dr] = x;
dr++;
pest[x] = 1;
lo[x] = val[x] = no;
no++;
int poz = ult[x];
while(poz != -1){
if(val[nod[poz]] == -1)
caut(nod[poz]);
if(pest[nod[poz]])
lo[x] = min2(lo[x], lo[nod[poz]]);
poz = next[poz];
}
int last, k;
if(lo[x] == val[x]){
prim[nr] = stiv[dr - 1];
last = stiv[dr - 1];
dr--;
while(last != x){
pest[last] = 0;
k = stiv[dr - 1];
urm[last] = k;
last = k;
dr--;
}
urm[x] = -1;
pest[x] = 0;
nr++;
}
}
int main(){
FILE *in = fopen("ctc.in", "r");
int n, m, i, x, y, dr = 0;
fscanf(in, "%d%d", &n, &m);
for(i = 0; i < n; i++){
ult[i] = -1;
val[i] = -1;
}
for(i = 0; i < m; i++){
fscanf(in, "%d%d", &x, &y);
x--; y--;
nod[dr] = y;
next[dr] = ult[x];
ult[x] = dr;
dr++;
}
fclose(in);
for(i = 0; i < n; i++){
if(val[i] == -1)
caut(i);
}
FILE *out = fopen("ctc.out", "w");
fprintf(out, "%d\n", nr);
int p;
for(i = 0; i < nr; i++){
p = prim[i];
while(p != -1){
fprintf(out, "%d ", p + 1);
p = urm[p];
}
fputc('\n', out);
}
fclose(out);
return 0;
}