Pagini recente » Cod sursa (job #1228940) | Cod sursa (job #171451) | Cod sursa (job #1131284) | Cod sursa (job #1761446) | Cod sursa (job #1279705)
#include <stdio.h>
using namespace std;
const int M=200420;
const int N=101337;
struct grafuri{int vf[M],urm[M],lst[N];}g1,g2;
int cnt;
int timp[N],cntt=1;
int sol[M], cnts=1;
bool viz[N];
int nr;
inline void adauga(int x, int y)
{
++nr;
g1.vf[nr]=y;
g1.urm[nr]=g1.lst[x];
g1.lst[x]=nr;
g2.vf[nr]=x;
g2.urm[nr]=g2.lst[y];
g2.lst[y]=nr;
}
void homodfs(int x)
{
viz[x]=false;
int y,p;
p=g2.lst[x];
sol[cnts++]=x;
while (p!=0)
{
y=g2.vf[p];
if(viz[y]) homodfs(y);
p=g2.urm[p];
}
}
void dfs(int x)
{
viz[x]=true;
int y,p;
p=g1.lst[x];
while (p!=0)
{
y=g1.vf[p];
if(!viz[y]) dfs(y);
p=g1.urm[p];
}
timp[cntt++]=x;
}
int main()
{
int n,m,x,y;
FILE * in, *out;
in=fopen ("ctc.in","r");
out=fopen ("ctc.out","w");
fscanf(in,"%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
fscanf(in,"%d%d",&x,&y);
adauga(x,y);
}
for(int i=1;i<=n;i++)
if(viz[i]==0)
dfs(i);
for(int i=cntt; i>0; i--)
if(viz[timp[i] ]==1)
{
cnt++;
homodfs(timp[i]);
sol[cnts++]=0;
}
fprintf(out,"%d\n",cnt);
for(int i=1; i<=cnts; i++)
{
if(sol[i]!=0) fprintf(out,"%d ",sol[i]);
else fprintf(out,"\n");
}
return 0;
}