Cod sursa(job #901550)

Utilizator alexteStefanescu Alexandru Catalin alexte Data 1 martie 2013 10:42:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
using namespace std;
int stiva[50002],viz[50002],start[50002],n,m,t[2][100002],k,stiva2[50002],j,i;
void citire()
{
    int i,a,b;
    ifstream fin("sortaret.in");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        k++;
        t[0][k]=b;
        t[1][k]=start[a];
        start[a]=k;
    }
}
void sortaret(int vf)
{
    int i,k=0;
    k++;
    stiva[k]=vf;
    viz[vf]=1;
    while(k>0)
    {
        i=start[stiva[k]];
        while(i!=0 && viz[t[0][i]])
            i=t[1][i];
        if(i!=0)
        {
            k++;
            stiva[k]=t[0][i];
            viz[t[0][i]]=1;
        }
        else
        {
            j++;
            stiva2[j]=stiva[k];
            k--;
        }
    }
}
int main()
{
    ofstream fout("sortaret.out");
    citire();
    for (i=1;i<=n;i++)
    {
        if (viz[i]==0)
        {
            sortaret(i);
        }
    }
    for(i=j;i>=1;--i)
        fout<<stiva2[i]<<' ';
    fout.close();
    return 0;
}