Cod sursa(job #2529444)

Utilizator tomitza.1604Sacuiu TomaAndrei tomitza.1604 Data 23 ianuarie 2020 15:28:35
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
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;
    int dr = -1;
    for(int i = 1; i <= n; i++){
        if(nrp[i] == 0){
            q[dr++] = i;
        }
    }
    while(st <= dr){
        x = q[st++];
        //pred x
        for(int p = lst[x]; p != 0; p = urm[p]){
            y = vf[p];
            nrp[y]--;
            if(nrp[y] == 0){
                q[++dr];
            }
        }
    }
    for(int i = 0; i <= dr; i++)
	{
        out << q[i] << " ";
    }
    return 0;
}