Pagini recente » Cod sursa (job #1351253) | Cod sursa (job #752949) | Cod sursa (job #51376) | Cod sursa (job #208058) | Cod sursa (job #1224366)
#include <fstream>
using namespace std;
#define MX 100100
int n,m,x[MX], y[MX], urm[MX], nr[MX],i, st[MX], dr[MX], v[MX], nrn, stiv[MX], nst ;
void adauga(int a)
{
int k=1;
if (nrn==0)
{ nrn=1;
v[1]=a;
return; }
while (k!=0 )
if (a==v[k] ) k=0;
else
if (a< v[k] )
{if (st[k] ) k= st[k];
else {v[++nrn]=a; st[k]=nrn; k=0; } }
else
{if (dr[k] ) k= dr[k];
else {v[++nrn]=a; dr[k]=nrn; k=0; } }
}
int gasit(int a)
{
int k=1;
if (nrn==0) return 0;
while ( k )
if (a==v[k] ) return 1;
else
if (a< v[k] )
k= st[k];
else k= dr[k];
return 0;
}
int main()
{
ifstream f1("sortaret.in");
ofstream f2("sortaret.out");
f1>>n>>m;
for (i=1; i<=m; i++)
f1>>x[i]>>y[i];
for (i=1; i<=m; i++)
{
urm[i]=i+1;
nr[x[i] ]++;
}
urm[m]=1;
for (i=1; i<=n; i++)
if (!nr[i])
{ stiv[++nst]=i;
adauga(i); }
int k=1, u;
while (k!=urm[k])
{ u= urm[k];
if (gasit(y[u]) )
{ urm[k]=urm[u]; //delete
nr[x[u] ]--;
if (nr[x[u] ]==0 ) {stiv[++nst]=x[u]; adauga(x[u] ); }
}
else k=urm[k];
}
stiv[++nst]=x[k];
while (nst>0)
{ f2<<stiv[nst]<<" ";
nst--; }
return 0;
}