Pagini recente » Cod sursa (job #426118) | Cod sursa (job #813413) | Cod sursa (job #1779819) | Cod sursa (job #177322) | Cod sursa (job #359466)
Cod sursa(job #359466)
#include<stdio.h>
#include<vector>
#define N 50001
using namespace std;
vector<int> v[N];
int n,i,L,g[N],h[N],p[N];
void read(),solve(),print(),hd(int T),hu(int F),sw(int A,int B);
int main()
{
read();
solve();
return 0;
}
void read()
{
int x,y;
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%d%d",&n,&i);
for(;i;i--){scanf("%d%d",&x,&y);g[y]++;v[x].push_back(y);}
for(i=1;i<=n;i++)h[i]=p[i]=i;
}
void solve()
{
for(i=n/2;i>=1;i--)hd(i);L=n;
for(i=1;i<=n;i++)print();printf("\n");
}
void hd(int T)
{
int F=T<<1;if(F>L)return;
if(F<L)if(g[h[F+1]]<g[h[F]])F++;if(g[h[F]]<g[h[T]]){sw(F,T);hd(F);}
}
void sw(int A,int B)
{
int aux=h[A];h[A]=h[B];h[B]=aux;
p[h[A]]=A;p[h[B]]=B;
}
void print()
{
int x;
vector<int>::iterator it;
x=h[1];sw(1,L);L--;hd(1);printf("%d ",x);
for(it=v[x].begin();it!=v[x].end();it++){g[*it]--;hu(p[*it]);}
}
void hu(int F)
{
int T=F>>1;if(!T) return;if(g[h[F]]<g[h[T]]){sw(F,T);hu(T);}
}