Cod sursa(job #2481816)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 27 octombrie 2019 14:22:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#define MAX 50001

using namespace std;

vector<int> graph[MAX];
int grad[MAX], C[MAX];

void Solve(int n)
{
    int i;

    for(i = 1; i <= n; i++)
        if(!grad[i])C[++C[0]] = i;


    for(i = 1; i <= n; i++)
    {
        for(auto nod : graph[C[i]])
        {
            grad[nod]--;

            if(!grad[nod])C[++C[0]] = nod;
        }
    }
}

int main()
{
    int n, m, i, a, b;

    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    fin >> n >> m;

    for(i = 1; i <= m; i++)
    {
        fin >> a >> b;

        graph[a].push_back(b);
        grad[b]++;
    }

    Solve(n);

    for(i = 1; i <= n; i++)fout << C[i] << " ";

    fin.close();
    fout.close();

    return 0;
}