Pagini recente » Cod sursa (job #262985) | Cod sursa (job #975402) | Cod sursa (job #1841813) | Cod sursa (job #2953581) | Cod sursa (job #1481136)
#include <stdio.h>
#define MAXN 100000
#define MAXM 200000
int k, sef, viz[MAXN+1], ok[MAXN+1], val[MAXM+1], e[MAXM+1], next[MAXM+1], urm[MAXM+1], lista[MAXN+1], list[MAXN+1], l[MAXN+1], last[MAXN+1], v[MAXN+1];
void dfs1(int x){
int p=lista[x];
viz[x]=1;
while(p){
if(viz[val[p]]==0){
dfs1(val[p]);
}
p=next[p];
}
v[k++]=x;
}
void dfs2(int x){
int p=list[x];
ok[x]=1;
last[x]=l[sef];
l[sef]=x;
while(p){
if(ok[e[p]]==0){
dfs2(e[p]);
}
p=urm[p];
}
}
int main(){
int n, m, i, ans;
FILE *fin, *fout;
fin=fopen("ctc.in", "r");
fout=fopen("ctc.out", "w");
fscanf(fin, "%d%d", &n, &m);
for(i=1; i<=m; i++){
fscanf(fin, "%d%d", &e[i], &val[i]);
next[i]=lista[e[i]];
lista[e[i]]=i;
urm[i]=list[val[i]];
list[val[i]]=i;
}
for(i=1; i<=n; i++){
if(viz[i]==0){
dfs1(i);
}
}
ans=0;
for(i=n-1; i>=0; i--){
if(ok[v[i]]==0){
sef=v[i];
dfs2(v[i]);
ans++;
}
}
fprintf(fout, "%d\n", ans);
for(i=1; i<=n; i++){
if(l[i]){
fprintf(fout, "%d", l[i]);
l[i]=last[l[i]];
while(l[i]){
fprintf(fout, " %d", l[i]);
l[i]=last[l[i]];
}
fprintf(fout, "\n");
}
}
fclose(fin);
fclose(fout);
return 0;
}