Cod sursa(job #2975400)

Utilizator Sorin123-21Enachioiu Sorin-Catalin Sorin123-21 Data 6 februarie 2023 13:59:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

struct degreeVertex{
    int inDegree = 0;
    int Vertex;
};

bool operator <(const degreeVertex &a, const degreeVertex &b){
    return a.inDegree > b.inDegree;
}

const int NMAX = 50001;
vector <int> vecinity[NMAX+3];
priority_queue<degreeVertex> pq;

int degree[NMAX+3];

bool contains(int from, int to){
    for(auto crt: vecinity[from]){
        if(crt == to){
            return true;
        }
    }
    return false;
}

int main()
{
    int n, m;

    in >> n >> m;

    for(int i = 0; i < m; i++){
        int from, to;
        in >> from >> to;
        if(!contains(from, to)){
            vecinity[from].push_back(to);
            degree[to]++;
        }
    }

    for(int i = 1; i <= n; i++){
        degreeVertex temp;
        temp.inDegree = degree[i];
        temp.Vertex = i;
        if(degree[i] == 0)
            pq.push(temp);
    }

    for(int i = 1; i <= n; i++){
        degreeVertex temp;
        temp.Vertex = pq.top().Vertex;
        temp.inDegree = pq.top().inDegree;
        pq.pop();
        for(auto aux: vecinity[temp.Vertex]){
            degree[aux]--;
            degreeVertex crt;
            crt.inDegree = degree[aux];
            crt.Vertex = aux;
            if(degree[aux] == 0)
                pq.push(crt);

        }
        out << temp.Vertex << " ";

    }

    return 0;
}