Cod sursa(job #2354842)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 25 februarie 2019 17:04:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N_MAX = 50000;
const int M_MAX = 100000;

int N, M;
vector<int> Edges[N_MAX + 1];
int Q[N_MAX + 1], rightt;
int deg[N_MAX + 1];

void sortaret() {
    //bagam la inceput nodurile care au gradul exterior 0
    for(int i = 1; i <= N; ++i)
        if(deg[i] == 0)
            Q[++rightt] = i;

    for(int i = 1; i <= N; ++i) {
        int x = Q[i];
        //scoatem arcele care pleaca din x si adaugam eventual nodurile cu gradul exterior 0
        for(auto y : Edges[x]) {
            --deg[y];
            if(deg[y] == 0)
                Q[++rightt] = y;
        }
    }
}

int main()
{
    int x, y;
    in >> N >> M;
    for(int i = 1; i <= M; ++i) {
        in >> x >> y;
        Edges[x].push_back(y);
        ++deg[y];
    }

    sortaret();

    for(int i = 1; i <= N; ++i)
        out << Q[i] << ' ';

    return 0;
}