Cod sursa(job #1699926)

Utilizator madalina41724Madalina Marin madalina41724 Data 8 mai 2016 20:49:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
const int N = 50005;
int n, m, nr = 0, urm[N*2], v[N*2], q[N], lst[N], d[N];

void Adauga(int x, int y)
{
    nr++;
    v[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void bts(){
    int p=0, u=0, x, y, poz;

    for(int i=1; i <= n; i++)
        if(d[i] == 0)
            q[u++] = i;

    while(p != u){
        x = q[p++];
        poz = lst[x];

        while(poz != 0){
            y = v[poz];
            d[y]--;

            if(d[y] == 0)
                q[u++] = y;
            poz = urm[poz];
        }
    }
}


int main()
{
    int i, x, y;
    in>>n>>m;
    for(i = 1; i <= m; i++){
        in>>x>>y;
        d[y]++;
        Adauga(x, y);
    }

    bts();

    for(i = 0; i < n; i++){
        out<<q[i]<<" ";
    }
    return 0;
}