Cod sursa(job #2581089)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 14 martie 2020 15:31:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
#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");

    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    srand(time(NULL));

    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;
}