Cod sursa(job #359466)

Utilizator proflaurianPanaete Adrian proflaurian Data 26 octombrie 2009 22:43:29
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#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);}
}