Cod sursa(job #2200532)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 1 mai 2018 18:05:32
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXIM = 50003;

vector <int> a[MAXIM];
int q[MAXIM], deg[MAXIM], N, M, a, b, u=-1, p=0;
int main()
{

    f >> N >> M;
    for (int i = 0; i < M; i++)
    {
        f >> a >> b;
        a[a].push_back(b);
        deg[b]++;
    }
    for (int i = 1; i <= N; i++) if (deg[i] == 0) q[++u] = i;
    while (p <= u)
    {
        int x = q[p], length=a[x].size();
        p++;
        for (int i = 0; i < length; i++)
        {
            deg[a[x][i]]--;
            if (deg[a[x][i]] == 0) q[++u] = a[x][i];
        }
    }
    for (int i = 0; i < N; i++) g << q[i] << ' ';
    return 0;
}