Pagini recente » Cod sursa (job #2743516) | Cod sursa (job #1633005) | Cod sursa (job #1350355) | Cod sursa (job #2034382) | Cod sursa (job #361484)
Cod sursa(job #361484)
#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();
v[nd]=0;
for( i = 0; i< dim; i++)
if(v[ t[nd][i] ]) DFST( t[nd][i] );
g[nr].pb( nd );
}
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=1; i<=n; i++)
if(v[i]==1) {nr++;DFST(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;
}