Cod sursa(job #352927)

Utilizator crisojogcristian ojog crisojog Data 3 octombrie 2009 19:27:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<stdio.h>
long n,m;
struct muc
{
	long i,j;
};muc q[100010];
long s[50001];

struct nod
{
	nod *urm;
	int info;
};

nod *t[50001];
long v[50001];

long part(long st,long dr)
{
	long i,j;
	muc aux,p;
	i=st-1;
	j=dr+1;
	p=q[(st+dr)/2];
	while (1)
	{
        do {i++;} while (q[i].i<p.i || (q[i].i==p.i && q[i].j<p.j));
        do {j--;} while (q[j].i>p.i || (q[j].i==p.i && q[j].j>p.j));
        if (i<j)
        {
			aux=q[i];
            q[i]=q[j];
            q[j]=aux;
		}
        else return j;
	}
}


void quicks(long st,long dr)
{
	long p;
	if (st<dr)
    {
		p=part(st,dr);
		quicks(st,p);
		quicks(p+1,dr);
    }
}

void InsertBegin(long a,long b)
{
	nod *aux;
	aux=new nod;
	aux->info=b;
	aux->urm=t[a];
	t[a]=aux;
}

void arce()
{
	long i;
	for (i=1;i<=m;i++)
	{
		if (q[i].i!=q[i-1].i || q[i].j!=q[i-1].j)
        {
			InsertBegin(q[i].i,q[i].j);
			v[q[i].j]++;
        }
    }
}

void parcurgere(int i)
{
	nod *p;
	for (p=t[i];p!=NULL;p=p->urm)
    {
		v[p->info]--;
    }
}

void sortare()
{
	long i,k;
	k=1;
	while (k)
	{
       k=0;
       for (i=1;i<=n;i++)
        {
            if (v[i]==0)
            {
                k=1;
                v[i]=-1;
                s[++s[0]]=i;
                parcurgere(i);
            }
        }
   }
}

void print()
{
	long i;
	for (i=s[0];i>=1;i--)
		printf("%ld ",s[i]);
}

int main()
{
	long i;
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;i++)
		scanf("%ld%ld",&q[i].j,&q[i].i);
	quicks(1,m);
	arce();
	sortare();
	print();
	return 0;
}