Cod sursa(job #1482340)

Utilizator bpalaniciPalanici Bogdan bpalanici Data 6 septembrie 2015 21:35:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

int n, m, grad_int[50005];
vector <int> graf[50005], coada;

void sort_topologic()
{
    coada.clear();
    coada.resize(n);
    for (int i = 1; i <= n; i++)
        if (!grad_int[i]) coada[0]++, coada[coada[0]] = i;
    for (int i = 1; i <= n; i++)
    {
        int nod = coada[i];
        for (const auto &it : graf[nod])
        {
            grad_int[it]--;
            if (!grad_int[it]) coada[0]++, coada[coada[0]] = it;
        }
    }
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1, a, b; i <= m; i++)
        scanf("%d %d", &a, &b), graf[a].push_back(b), grad_int[b]++;
    sort_topologic();
    for (int i = 1; i <= n; i++)
        printf("%d ", coada[i]);
    return 0;
}