Cod sursa(job #2326037)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 23 ianuarie 2019 12:04:40
Problema Sortare topologica Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 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;
bool Viz[MAXN];
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] && !Viz[x])
        {
            Viz[x] = true;
            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;
}