Cod sursa(job #2195484)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 16 aprilie 2018 15:26:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;
ifstream in ("sortaret.in");
ofstream out ("sortaret.out");
int start[100001],t[2][300005],r[100005],n,m,f[100005],timp=0;
void citire ()
{
    in>>n>>m;
    int i,k=0,a,b;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        k++;
        t[0][k]=b;
        t[1][k]=start[a];
        start[a]=k;
    }
}
void recur (int poz)
{
        r[poz]=1;
        for(int i=start[poz];i!=0;i=t[1][i])
        {
            if(r[t[0][i]]==0)
                recur(t[0][i]);
        }
        timp++;
        f[poz]=timp;
}
int main()
{
    int i,cnt=0;
    citire();
    for(i=1;i<=n;i++)
    {
        if(r[i]==0)
            recur(i);
    }
    for(i=1;i<=n;i++)
        r[n+1-f[i]]=i;
    for(i=1;i<=n;i++)
        out<<r[i]<<' ';
    return 0;
}