Cod sursa(job #1172309)

Utilizator TataruTataru Mihai Tataru Data 17 aprilie 2014 12:05:47
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#define inFile "sortaret.in"
#define outFile "sortaret.out"

using namespace std;

int n,m,a[100003],b[100003],rez[50003],k,apar[50003],aparRez[50005];

void dreapta(int nr)
{
    int i=0,nr1;
    while(apar[nr] && i<=m)
    {
        i++;
        if(b[i]==nr)
        {
            apar[nr]--;
            nr1=a[i];
            a[i]=0;
            if(apar[nr1]>0)
                dreapta(nr1);
        }
    }
    if(!aparRez[nr])
    {
        rez[++k]=nr;
        aparRez[nr]=1;
    }
}

void stanga(int iW)
{
    int i,nr;
    for(i=iW;i<=m;i++)
        if(a[i])
        {
            nr=a[i];
            a[i]=0;
            dreapta(nr);
            nr=b[i];
            b[i]=0;
            dreapta(nr);
        }
}

int main()
{
    int i;
    ifstream fin(inFile);
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a[i]>>b[i];
        apar[b[i]]++;
    }
    fin.close();

    stanga(1);

    ofstream fout(outFile);
    for(i=1;i<=n;i++)
        fout<<rez[i]<<" ";
    fout.close();
}