Cod sursa(job #2668610)

Utilizator OrzataAndreiOrzata Andrei OrzataAndrei Data 5 noiembrie 2020 03:59:23
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAX 50010

using namespace std;

int N, M, gradEx[MAX], Q[MAX];
vector<int> Grade[MAX];

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

void citire()
{
    int a, b;

    in>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        in>>a>>b;
        Grade[a].push_back(b);
        gradEx[b]++;
    }
}

void afisare()
{
    for(int i = 1; i <= N; i++)
        out<<Q[i]<<" ";
}

void rezolvare()
{

    vector<int>::iterator it;

    for(int i = 1; i <= N; i++)
        if(gradEx[i] == 0)
            Q[++Q[0]] = i;

    for(int i = 1; i <= N; i++)
    {
        int x = Q[i];
        for(it = Grade[x].begin(); it != Grade[x].end(); ++it)
        {
            gradEx[*it]--;
            if(gradEx[*it] == 0)
                Q[++Q[0]] = *it;
        }
    }
}
int main()
{

    citire();
    rezolvare();
    afisare();

    return 0;
}