Cod sursa(job #2200535)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 1 mai 2018 18:06:31
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.f");
ofstream g("sortaret.g");

const int MAXIM = 50003;

vector <int> v[MAXIM];
int n, m, a, b, u=-1, p=0, q[MAXIM], deg[MAXIM];\
int main()
{

    f >> n >> m;
    for (int i = 0; i < m; i++)
    {
        f >> a >> b;
        v[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=v[x].size();
        p++;
        for (int i = 0; i < length; i++)
        {
            deg[v[x][i]]--;
            if (deg[v[x][i]] == 0) q[++u] = v[x][i];
        }
    }
    for (int i = 0; i < n; i++) g << q[i] << ' ';
    return 0;
}