Pagini recente » Cod sursa (job #408616) | Cod sursa (job #405475) | Cod sursa (job #1907704) | Cod sursa (job #2710098) | Cod sursa (job #977689)
Cod sursa(job #977689)
#include <iostream>
#include <fstream>
using namespace std;
ofstream g("ctc.out");
int v[100001],vr[200001],kr,nr;
struct la
{
la *urm;
int ind;
} *p1,*q;
struct nod
{
la *urm;
int b;
int index,mn;
} vnod[100001];
int index1,nv,n,m,i,x,y;
void analyze(int pos)
{
vnod[pos].b=1;
index1++;
nv++;
v[nv]=pos;
la *p;
p=vnod[pos].urm;
vnod[pos].index=index1;
vnod[pos].mn=index1;
while (p!=NULL)
{
if (vnod[p->ind].b==0)
analyze(p->ind);
vnod[pos].mn=min(vnod[pos].mn,vnod[p->ind].mn);
p=p->urm;
}
if (vnod[pos].index==vnod[pos].mn)
{
kr++;
while (v[nv]!=pos)
{
nr++;
vr[nr]=v[nv];
vnod[v[nv]].mn=999999999;
v[nv]=0;
nv--;
}
nr++;
vr[nr]=v[nv];
v[nv]=0;
nv--;
nr++;
vr[nr]=-1;
}
}
int main(void)
{
FILE * f;
f=fopen("ctc.in","r");
fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++)
{
fscanf(f,"%d%d",&x,&y);
if (vnod[x].urm==NULL)
{
p1=new(la);
p1->ind=y;
vnod[x].urm=p1;
p1->urm=NULL;
}
else
{
q=vnod[x].urm;
while (q->urm!=NULL)
q=q->urm;
p1=new(la);
p1->ind=y;
p1->urm=NULL;
q->urm=p1;
}
}
for (i=1;i<=n;i++)
if (vnod[i].b==0)
analyze(i);
g<<kr<<'\n';
for (i=1;i<=nr;i++)
if (vr[i]==-1)
g<<'\n';
else
g<<vr[i]<<' ';
g.close();
return 0;
}