Pagini recente » Cod sursa (job #1189066) | Cod sursa (job #2368448) | Cod sursa (job #2648409) | Cod sursa (job #1116635) | Cod sursa (job #2539971)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N= 100001;
const int M= 200001;
int stiva[N],cnt,stiva_inv[N];
int lst[N],vf[2*M] , urm[2*M], n , nr ;
int lst_inv[N], vf_inv[2*M],urm_inv[2*M],viz_inv[N];
int ans[2*N+1],anspos;
bool viz[N];
void dfs_top(int x)
{
viz[x]=true;
int y;
for(int p=lst[x]; p!=0 ; p=urm[p])
{
y=vf[p];
if(!viz[y])
dfs_top(y);
}
stiva[++cnt]=x;
}
void dfs_top_inv(int x)
{
viz_inv[x]=true;
ans[anspos++]=x;
int y;
for(int p=lst_inv[x];p!=0;p=urm_inv[p])
{
y=vf_inv[p];
if( !viz_inv[y])
dfs_top_inv(y);
}
stiva_inv[++cnt]=x;
}
void adauga (int x, int y )
{
++nr;
vf[nr]=y;
urm[nr]=lst[x];
lst[x]=nr;
vf_inv[nr]=x;
urm_inv[nr]=lst_inv[y];
lst_inv[y]=nr;
}
int main()
{
int n,m,x,y;
in>>n>>m;
for(int i=0;i<m;i++)
{
in>>x>>y;
adauga(x,y);
}
for(int i=1;i<=n;i++)
{
if(!viz[i])
dfs_top(i);
}
cnt=0;
int nrof=0;
for(int i=n;i>0;i--)
{
if(!viz_inv[stiva[i]])
{
dfs_top_inv(stiva[i]);
ans[anspos]=-1;
++nrof;
}
}
out<<nrof<<'\n';
for(int i=0;i< anspos;i++)
{
if(ans[i] == -1)
out<<'\n';
else
out<<ans[i]<<" ";
}
return 0;
}