Cod sursa(job #2526128)

Utilizator AndreeaGherghescuAndreea Gherghescu AndreeaGherghescu Data 18 ianuarie 2020 12:02:42
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("sortaret.in");
ofstream out ("sortaret.out");

const int N=50002;
const int M=100002;
int lst[N],urm[M],pred[N],vf[M],nr,q[N];

void adauga (int x, int y)
{
    vf[++nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}
int main()
{
    int x,y,n,m;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        in>>x>>y;
        adauga (x,y);
        pred[y]++;
    }
    int st=0,dr=-1;
    for (int i=1;i<=n;i++)
    {
        if (pred[i]==0)
            q[++dr]=i;
    }
    while (st<=dr)
    {
        x=q[st++];
        for (int p=lst[x];p!=0;p=urm[p])
        {
            y=vf[p];
            pred[y]--;
            if (pred[y]==0)
                q[++dr]=y;
        }
    }
    for (int i=0;i<n;i++)
        out<<q[i]<<' ';
    return 0;
}