Cod sursa(job #356974)
#include<iostream>
using namespace std;
//definim clasa nod
class nod
{
public:
int nr;
int noduri;
int stg;
int drp;
int intrari;
nod *urmator;
nod *ultim;
nod(void):nr(0),noduri(0),stg(0),drp(0),intrari(0),urmator(NULL),ultim(NULL){};
};
//definim lista
nod v[50001];
int main(void)
{
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
int n,m,i,x,y;
cin>>n>>m;
//creem vectorul cu listele de noduri
for(i=1; i<=m; i++)
{
cin>>x>>y;
if(v[x].noduri==0)
{
nod *var=new nod;
var->nr=y;
var->urmator=NULL;
v[x].noduri=1;
v[x].urmator=var;
v[y].intrari++;
v[x].ultim=v[x].urmator;
}
else
{
nod *var=new nod;
var->nr=y;
var->urmator=NULL;
v[x].ultim->urmator=var;
v[x].ultim=var;
v[x].noduri++;
v[y].intrari++;
}
}
//initializam drp-urile
for(i=2; i<=n-1; i++){v[i].drp=i+1; v[i].stg=i-1;}
v[1].drp=2; v[n].stg=n-1;
int noduri=n;
int primul=1;
while(n)
{
int aux=primul;
for(i=1; i<=n; i++)
{
if(v[aux].intrari==0)
{ cout<<aux<<" ";
if(v[aux].noduri){ int k=v[aux].noduri;
nod *r=v[aux].urmator;
while(k)
{
int auxiliar=r->nr;
v[auxiliar].intrari--;
r=r->urmator;
k--;
}
}
//mai sus, daca mai are noduri, le decrementam pe toate
if(primul==aux)primul=v[aux].drp; noduri--; if(v[aux].stg && v[aux].drp){ v[v[aux].stg].drp=v[aux].drp;
v[v[aux].drp].stg=v[aux].stg;
}
}
aux=v[aux].drp;
}
n=noduri;
}
return 0;
}