Cod sursa(job #324816)

Utilizator IoannaPandele Ioana Ioanna Data 17 iunie 2009 15:15:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<stdio.h>
long n,m;
typedef struct {long i,j;}muchii;
muchii q[100010];
long s[50001];

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

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

void read()
{
scanf("%ld%ld",&n,&m);
long i;
for (i=1;i<=m;i++)
    scanf("%ld%ld",&q[i].j,&q[i].i);
}

long part(long st,long dr)
{
long i,j;
muchii 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()
{
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
read();
quicks(1,m);
arce();
sortare();
print();
return 0;
}