Cod sursa(job #1359017)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 24 februarie 2015 20:57:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<stdio.h>
#include<list>

int ind[50001],n,m;
bool been[50001];

using namespace std;

int main()
{
    FILE *fin,*fout;
    fin=fopen("sortaret.in","r");
    fout=fopen("sortaret.out","w");

    int t1,t2;
    fscanf(fin,"%d %d",&n,&m);

    list<int> ready;
    list<int> *a;

    a=new list<int>[n+1];

    for(int i=1;i<=m;i++)
    {
        fscanf(fin,"%d %d",&t1,&t2);
        a[t1].push_front(t2);
        ind[t2]++;
    }

    for(int i=1;i<=n;i++)
    {
        if(ind[i]==0&&been[i]==0)
        {
            been[i]=1;
            ready.push_front(i);
            fprintf(fout,"%d ",ready.front());
        }
    }
    while(!ready.empty())
    {
        while(!ready.empty())
        {
            while(!a[ready.back()].empty())
            {
                ind[a[ready.back()].back()]--;
                a[ready.back()].pop_back();
            }
            ready.pop_back();
        }
        for(int i=1;i<=n;i++)
        {
            if(ind[i]==0&&been[i]==0)
            {
                been[i]=1;
                ready.push_front(i);
                fprintf(fout,"%d ",ready.front());
            }
        }
    }
}