Cod sursa(job #2533669)

Utilizator valeriucaraselCarasel Valeriu valeriucarasel Data 29 ianuarie 2020 15:52:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N=50001,M=100001;

int vf[M], nrp[N], urm[M], lst[N], q[N],nr;

void adauga(int x, int y)
{
    vf[++nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
    nrp[y]++;
}

int main()
{
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    int n,m;
    int x,y;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        in>>x>>y;
        adauga(x,y);
    }
    int st=0,dr=-1;
    for (int i=1;i<=n;i++)
    {
        if (nrp[i]==0)
        {
            q[++dr]=i;
        }
    }
    while (st<=dr)
    {
        x=q[st++];
        out << x << ' ';
        for (int p=lst[x];p!=0;p=urm[p])
        {
            y=vf[p];
            if (--nrp[y]==0)
            {
                q[++dr]=y;
            }
        }
    }

    in.close();
    out.close();
    return 0;
}