Cod sursa(job #903403)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 1 martie 2013 20:30:20
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream f;
ofstream g;
int n,m,start[50002],t[2][100001],viz[50002],stiva2[50002],j;
void df(int vfstart)
{
    int stiva[10001],k,i;
    for(i=1;i<=n;i++)
    viz[i]=0;
    stiva[1]=vfstart;
    k=1;
    viz[vfstart]=1;
    while(k>0)
    {
        i=start[stiva[k]];
        while(i!=0 && viz[t[0][i]]==1)
        i=t[1][i];
        if(i!=0)
        {
            k++;
            stiva[k]=t[0][i];
            viz[t[0][i]]=1;
        }
        else {stiva2[++j]=stiva[k];--k;}
    }
}
int main()
{
    int i,x,y,k=0;
    f.open("sortaret.in");
    g.open("sortaret.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        ++k;
        t[0][k]=y;
        t[1][k]=start[x];
        start[x]=k;
    }
    for(i=1;i<=n;i++)
    if(viz[i]==0)
        df(i);
    for(i=n;i>=1;--i)
        g<<stiva2[i]<<" ";
    return 0;
}