Cod sursa(job #2529447)

Utilizator tomitza.1604Sacuiu TomaAndrei tomitza.1604 Data 23 ianuarie 2020 15:31:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <iostream>

using namespace std;

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

const int N = 50001, M = 100001;
int vf[M], urm[M], lst[N], q[N], nrp[N], nr;

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

}

int main()
{
    int n, m, m1, m2, x, y;
    in >> n >> m;
    for(int  i = 1; i <= m; i++)
    {
        in >> m1 >> m2;
        adauga(m1, m2);
        nrp[m2]++;
    }
    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++];
        for(int p = lst[x]; p != 0; p = urm[p])
        {
            y = vf[p];
            nrp[y]--;
            if(nrp[y] == 0)
            {
                q[++dr] = y;
            }
        }
    }
    for(int i = 0; i <= dr; i++)
        out << q[i] << " ";
    return 0;

}