Cod sursa(job #2509909)

Utilizator MichaelXcXCiuciulete Mihai MichaelXcX Data 15 decembrie 2019 10:35:44
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int NMAX = 50005;

int N, M, Q[NMAX], deg[NMAX];
vector < int > G[NMAX];

void Read()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        deg[y]++;
    }
}

void Write()
{
    for(int i = 1; i <= N; i++)
        fout << Q[i] << " ";
}

void Sol()
{
    int x;
    vector < int >::iterator it;
    for(x = 1; x <= N; x++)
        if(deg[x] == 0)
            Q[++Q[0]] = x;

    for(int i = 1; i <= N; i++) {
        x = Q[i];
        for(it = G[x].begin(); it != G[x].end(); it++) {
            deg[*it]--;
            if(deg[*it] == 0)
                Q[++Q[0]] = *it;
        }
    }
}

int main()
{
    Read();
    Sol();
    Write();
}