Cod sursa(job #901487)

Utilizator alexteStefanescu Alexandru Catalin alexte Data 1 martie 2013 10:26:02
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
using namespace std;
int stiva[100002],viz[100002],start[100002],n,m,t[2][100002],k,stiva2[100002],j;
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()
{
    ofstream fout("sortaret.out");
    int vf=1,i,j=0,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--;
        }
    }
    for(i=j;i>=1;--i)
        fout<<stiva2[i]<<' ';
    fout.close();
}
int main()
{
    citire();
    sortaret();
    return 0;
}