Cod sursa(job #2843671)

Utilizator mediocrekarmaChirvasa George Matei mediocrekarma Data 2 februarie 2022 19:21:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
//#include "pch.h"
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");


const int N_MAX = 50000;
vector<int> v[N_MAX + 1];
int exteriorGrade[N_MAX + 1];

void topologicalSort(vector<int>& q, const int& n) {
    q.reserve(n);
    for (int i = 1; i <= n; ++i) {
        if (!exteriorGrade[i]) {
            q.push_back(i);
        }
    }
    for (int i = 0; i < n; ++i) {
        for (const int& index : v[q[i]]) {
            if (!--exteriorGrade[index])
                q.push_back(index);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    fin.tie(0);
    int n, m;
    fin >> n >> m;
    while (m--) {
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
        ++exteriorGrade[y];
    }
    vector<int> q;
    topologicalSort(q, n);
    for (const int& x : q) {
        fout << x << ' ';
    }
}