Pagini recente » Rating Stefania Mocan (stefi99) | Istoria paginii utilizator/my_raluca_21 | Istoria paginii utilizator/eto5072 | Diferente pentru schimbare-borland/argumentatie intre reviziile 3 si 2 | Cod sursa (job #361489)
Cod sursa(job #361489)
#include<stdio.h>
#include<vector>
#define max 100001
#define pb push_back
using namespace std;
vector <vector <int> > g(max);
vector <vector <int> > t(max);
vector <vector <int> > s(max);
int n,m,nr,k,v[max],d[max];
void DATA(){
int x,y;
FILE *f=fopen("ctc.in","r");
fscanf(f,"%d%d",&n,&m);
for( ; m-- ; ){
fscanf(f,"%d%d",&x,&y);
g[x].pb(y);
t[y].pb(x);
}
}
void DFS( int nd ){
int i,dim=g[nd].size();
v[nd]=1;
for( i = 0; i< dim; i++)
if( ! v[ g[nd][i] ] ) DFS( g[nd][i] );
d[++k] = nd;
}
void DFST( int nd ){
int i,dim=t[nd].size();
s[nr].pb( nd );
v[nd]=0;
for( i = 0; i< dim; i++)
if(v[ t[nd][i] ]) DFST( t[nd][i] );
}
int main(){
FILE *o=fopen("ctc.out","w");
DATA();
int i,j,dim;
for(i=1;i<=n;i++)
if(!v[i]) DFS(i);
for(i=n; i>0; i--)
if(v[d[i]]==1) {nr++;DFST(d[i]);}
fprintf(o,"%d\n",nr);
for(i=1;i<=nr;i++){ dim=s[i].size();
for(j=0;j<dim;j++) fprintf(o,"%d ",s[i][j]);
fprintf(o,"\n");
}
return 0;
}