Cod sursa(job #1224366)

Utilizator RaileanuCristian Raileanu Raileanu Data 30 august 2014 18:34:55
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>

using namespace std;
#define MX 100100

int n,m,x[MX], y[MX], urm[MX], nr[MX],i, st[MX], dr[MX], v[MX], nrn, stiv[MX], nst ;

void adauga(int a)
{
    int k=1;
    if (nrn==0)
    { nrn=1;
      v[1]=a;
      return; }

    while (k!=0 )
     if (a==v[k] ) k=0;
      else
      if (a< v[k] )
         {if (st[k] ) k= st[k];
          else {v[++nrn]=a; st[k]=nrn; k=0; } }
        else
         {if (dr[k] ) k= dr[k];
          else {v[++nrn]=a; dr[k]=nrn; k=0; } }
}

int gasit(int a)
{
    int k=1;
    if (nrn==0) return 0;

    while ( k )
        if (a==v[k] ) return 1;
          else
            if (a< v[k] )
                 k= st[k];
            else  k= dr[k];

    return 0;
}

int main()
{
    ifstream f1("sortaret.in");
    ofstream f2("sortaret.out");
    f1>>n>>m;
    for (i=1; i<=m; i++)
        f1>>x[i]>>y[i];

    for (i=1; i<=m; i++)
    {
        urm[i]=i+1;
        nr[x[i] ]++;
    }
    urm[m]=1;

    for (i=1; i<=n; i++)
        if (!nr[i])
    {  stiv[++nst]=i;
       adauga(i); }

    int k=1, u;
    while (k!=urm[k])
    {   u= urm[k];
        if (gasit(y[u]) )
        { urm[k]=urm[u]; //delete
          nr[x[u] ]--;
          if (nr[x[u] ]==0 ) {stiv[++nst]=x[u]; adauga(x[u] ); }
        }
        else k=urm[k];
    }
    stiv[++nst]=x[k];

    while (nst>0)
    { f2<<stiv[nst]<<" ";
      nst--;  }

    return 0;
}