Cod sursa(job #1997463)

Utilizator AndreiDumitrescuAndrei Dumitrescu AndreiDumitrescu Data 4 iulie 2017 13:38:45
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int INF = 50001;
const int N = 50001;
const int M = 100001;

int nr, n, m;
int lst[N], d[N], nrp[N], q[N];
int vf[2*M], urm[2*M];

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

void actualizare(int x){
    int p = lst[x], y;
    while(p != 0){
        y = vf[p];
        ///--d[y];
        p = urm[p];
    }
    d[x] = INF;
}

int main()
{
    f >> n >> m;
    int i, p = 0, u = -1,x,y;
    for(i = 0 ; i < m; i++){
        f >> x >> y;
        adauga(x, y);
    }
    for(i = 1 ; i <= n; i++)
    {
        if(nrp[i] == 0){
            q[++u] = i;
        }
    }
    while(p <= u)
    {
        x = q[p++];
        int poz = lst[x];
        while(poz != 0)
        {
            y = vf[poz];
            --nrp[y];
            if(nrp[y] == 0){
                q[++u] = y;
            }
            poz = urm[poz];
        }
    }
    for(i = 1 ; i <= n ; i++)
        g << q[i] << " ";
}