Cod sursa(job #1820293)

Utilizator dranoellenTurica Leonard-Petru dranoellen Data 1 decembrie 2016 15:42:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <vector>
#include <cstdio>

using namespace std;
vector <int> nr[50100];
int grad[50100],coada[50100],shir[50100];
int main()
{
    int n,m,a,b;
    FILE *out=fopen("sortaret.out","w"),
          *in=fopen("sortaret.in","r");
    fscanf(in,"%d%d",&n,&m);
    while(m--)
    {
        fscanf(in,"%d%d",&a,&b);
        nr[a].push_back(b);
        grad[b]++;
    }
    for(int i=1; i<=n; ++i)if(!grad[i])coada[++coada[0]]=i;

    for(int i=1; i<=coada[0]; ++i)
    {
        shir[++shir[0]]=coada[i];
        vector<int>::iterator x;
        x=nr[coada[i]].begin();
        while(x!=nr[coada[i]].end())
        {
            --grad[*x];
            if(!grad[*x])coada[++coada[0]]=*x;
            ++x;
        }
    }
    for(int i=1;i<=shir[0];++i)
        fprintf(out,"%d ",shir[i]);
    return 0;
}