Pagini recente » Cod sursa (job #2961078) | Cod sursa (job #1647910) | Cod sursa (job #1984235) | Cod sursa (job #803276) | Cod sursa (job #283823)
Cod sursa(job #283823)
#include<stdio.h>
#define nmax 100111
struct nod { int inf; nod *urm;} *v1[nmax], *v2[nmax], *sol[nmax];
int n, m, x, y, i, viz[nmax], st[nmax], u, nrctc;
void citire(){
FILE *f = fopen("ctc.in", "r");
fscanf(f,"%d %d",&n,&m);
for(i=1; i<=m; i++){
fscanf(f,"%d %d",&x,&y);
nod *p = new nod; p->inf = y; p->urm = v1[x]; v1[x] = p;
nod *q = new nod; q->inf = x; q->urm = v2[y]; v2[y] = q;
}
fclose(f);
}
void DFS1(int nc){
viz[nc] = 1;
nod *p;
for(p = v1[nc]; p != NULL; p = p->urm)
if( !viz[ p->inf ] )
DFS1( p->inf );
st[++u] = nc;
}
void DFS2(int nc){
viz[nc] = 2;
nod *q = new nod;
q->inf = nc; q->urm = sol[nrctc]; sol[nrctc] = q;
nod *p;
for( p = v2[nc]; p != NULL; p = p->urm )
if( viz[ p->inf ] != 2 )
DFS2(p->inf);
}
void solve(){
int i;
for(i=1; i<=n; i++)
if( !viz[i] )
DFS1(i);
for(i=n; i>=1; i--)
if( viz[st[i]] != 2 ){
nrctc++;
DFS2(st[i]);
}
}
void afisare(){
nod *p;
FILE *g = fopen("ctc.out","w");
fprintf(g,"%d\n",nrctc);
for(i=1; i<=nrctc; i++){
for(p = sol[i]; p != NULL; p = p->urm)
fprintf(g,"%d ",p->inf);
fprintf(g,"\n");
}
fclose(g);
}
int main(){
citire();
solve();
afisare();
return 0;
}