Cod sursa(job #2368335)

Utilizator andreisavulescuSavulescu Andrei andreisavulescu Data 5 martie 2019 15:33:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N_MAX = 50000;
const int M_MAX = 100000;

int N, M;

struct nod
{
    int info;
    nod *urm;
};

nod *v[100001];

int Q[N_MAX + 1], u; ///Coada
int gr[N_MAX + 1];

void add(int x, int y)
{
    nod *p = new nod;
    p->info = y;
    p->urm = v[x];
    v[x] = p;
}

void sortaret()
{
    ///Punem la inceput nodurile care au gradul exterior 0
    for(int i = 1; i <= N; ++i)
        if(gr[i] == 0)
            Q[++u] = i;
    for(int i = 1; i <= N; ++i)
    {
        int x = Q[i];
        ///Scoatem arcele care pleaca din x si adaugam
        ///eventual nodurile cu gradul exterior 0
        for(nod *p = v[x]; p != NULL; p = p->urm)
        {
            int y = p->info;
            gr[y]--;
            if(gr[y] == 0)
                Q[++u] = y;
        }
    }
}

void citire()
{
    int x, y;
    f >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        f >> x >> y;
        add(x, y);
        gr[y]++;
    }
}

int main()
{
    citire();
    sortaret();
    for(int i = 1; i <= N; ++i)
        g << Q[i] << ' ';
    return 0;
}