Pagini recente » Cod sursa (job #2460560) | Cod sursa (job #717805) | Cod sursa (job #481581) | Cod sursa (job #3271398) | Cod sursa (job #1708344)
#include <fstream>
using namespace std;
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
int t[2][200001],t1[2][200001],viz[100001],n,m,st[100001],vf,nr,start[200001],start1[200001];
void citire ()
{
cin>>n>>m; int x,y;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
t[0][i]=y;
t[1][i]=start[x];
start[x]=i;
t1[0][i]=x;
t1[1][i]=start1[y];
start1[y]=i;
}
}
void dfs1 (int nod)
{
viz[nod]=1;
int x=start[nod];
while(x!=0)
{
if(viz[t[0][x]]==0)
dfs1(t[0][x]);
x=t[1][x];
}
vf++; st[vf]=nod;
}
void dfs2 (int nod)
{
viz[nod]=2;
int x=start1[nod];
while(x!=0)
{
if(viz[t1[0][x]]==1)
dfs2(t1[0][x]);
x=t1[1][x];
}
}
void dfs3 (int nod)
{
viz[nod]=3;
int x=start1[nod];
cout<<nod<<" ";
while(x!=0)
{
if(viz[t1[0][x]]==2)
dfs3(t1[0][x]);
x=t1[1][x];
}
}
int main()
{
citire();
for(int i=1;i<=n;i++)
if(viz[i]==0)
dfs1(i);
for(int i=vf;i>=1;i--)
if(viz[st[i]]==1)
dfs2(st[i]),nr++;
cout<<nr<<"\n";
for(int i=vf;i>=1;i--)
if(viz[st[i]]==2)
dfs3(st[i]),cout<<"\n";
return 0;
}