Cod sursa(job #2325989)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 23 ianuarie 2019 11:45:19
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int MAXN = 50000 + 16;
int Deg[MAXN], N, M;
vector < int > Suc[MAXN];

int main()
{
    fin >> N >> M;
    while(M--)
    {
        int from, to;
        fin >> from >> to;
        ++Deg[to];
        Suc[from].push_back(to);
    }

    int x = 1;
    while(x <= N)
    {
        if(!Deg[x])
        {
            fout << x << ' ';
            vector < int > :: iterator it;
            int node = x;
            for(it = Suc[node].begin();
                it != Suc[node].end(); ++it)
            {
                --Deg[*it];
                if(!Deg[*it] && *it < x + 1)
                    x = *it - 1;
            }

        }
        ++x;
    }

    return 0;
}