Cod sursa(job #2969903)

Utilizator GeorgeNistorNistor Gheorghe GeorgeNistor Data 23 ianuarie 2023 21:08:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
/*
 * https://www.infoarena.ro/problema/sortaret 100p
 * O(V+E)
 */
#include <bits/stdc++.h>

using namespace std;

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

int V, E;
vector<vector<int>> adjList;
vector<int> inDegree;

void init(){
    adjList.resize(V+1);
    inDegree.resize(V+1);
}

void read(){
    in >> V >> E;
    init();
    for(int i = 0; i < E; i++){
        int u, v;
        in >> u >> v;
        adjList[u].push_back(v);
        inDegree[v]++;
    }
}

void topologicalSorting(){
    queue<int> q;
    for(int i = 1; i <= V; i++)
        if(!inDegree[i])
            q.push(i);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        out << u << ' ';
        for(auto v: adjList[u]){
            inDegree[v]--;
            if(!inDegree[v])
                q.push(v);
        }
    }
}

int main() {
    read();
    topologicalSorting();
    return 0;
}