Pagini recente » Cod sursa (job #3041783) | Cod sursa (job #711798) | Rating Filip Popp (Filip_Rush) | Cod sursa (job #487724) | Cod sursa (job #361486)
Cod sursa(job #361486)
#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);
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();
g[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);
g.clear();
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=g[i].size();
for(j=0;j<dim;j++) fprintf(o,"%d ",g[i][j]);
fprintf(o,"\n");
}
return 0;
}