Pagini recente » Cod sursa (job #424254) | Cod sursa (job #829860) | Cod sursa (job #1113234) | Cod sursa (job #2442424) | Cod sursa (job #1261765)
#include <cstdio>
FILE* in=fopen("ctc.in","r");
FILE* out=fopen("ctc.out","w");
int n,m;
const int Q=100002,W=200004;
int lst[Q],nxt[W],val[W],nr;
void add(int a, int b)
{
nr++;
val[nr]=b;
nxt[nr]=lst[a];
lst[a]=nr;
}
int viz[Q];
int nrs;
int go[Q],wh[Q];
int tat[Q];
int num;
int st[Q],nst;
void dfs(int nod)
{
int p=lst[nod];
viz[nod]=++num;
go[nod]=nod;
st[++nst]=nod;
while(p)
{
if(viz[val[p]]!=0 && wh[val[p]]==0)
{
if(viz[go[nod] ] > viz[ val[p] ])
{
go[nod]=val[p];
}
}
if(viz[val[p]]==0)
{
tat[val[p]]=nod;
dfs(val[p]);
}
p=nxt[p];
}
wh[nod]=++nrs;
}
int main()
{
fscanf(in,"%d%d",&n,&m);
int a,b;
for(int i=1; i<=m; i++)
{
fscanf(in,"%d%d",&a,&b);
add(a,b);
}
for(int i=1; i<=n; i++)
{
if(viz[i]==0)
dfs(i);
}
int act=st[nst];
int rez=0;
while(act!=0)
{
if(go[act]!=act)
{
act=go[act];
}
else
{
rez++;
act=st[viz[act]-1];
}
}
fprintf(out,"%d\n",rez);
act=nst;
int nxt=st[nst];
while(go[nxt]!=nxt)
nxt=go[nxt];
for(; act>0; act--)
{
if(st[act]==nxt)
{
fprintf(out,"%d\n",st[act]);
nxt=st[viz[nxt]-1];
while(go[nxt]!=nxt)
nxt=go[nxt];
}
else
fprintf(out,"%d ",st[act]);
}
/*
act=st[nst];
int nxt=act;
while(go[nxt]!=nxt)
{
nxt=go[nxt];
}
for(; act>0; act--)
{
if(act==nxt)
{
fprintf(out,"%d\n",st[act]);
nxt=st[viz[nxt]-1];
while(go[nxt]!=nxt)
nxt=go[nxt];
}
else
fprintf(out,"%d ",st[act]);
}
*/
return 0;
}