Cod sursa(job #3260246)

Utilizator PreparationTurturica Eric Preparation Data 1 decembrie 2024 11:38:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#define MAX_N 50005

using namespace std;

vector<int> v[MAX_N];
int countt[MAX_N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

int main()
{
    FILE *fin = fopen("sortaret.in", "r");
    FILE *fout = fopen("sortaret.out", "w");
    int n, m;
    fscanf(fin, "%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        fscanf(fin, "%d %d\n", &a, &b);
        a--;
        b--;
        v[a].push_back(b);
        countt[b]++;
    }
    for (int i = 0; i < n; i++)
        pq.push({countt[i], i});
    while (!pq.empty()) {
        auto tp = pq.top();
        pq.pop();
        if (countt[tp.second] != tp.first)
            continue;
        for (auto j: v[tp.second]) {
            countt[j]--;
            pq.push({countt[j], j});
        }
        fprintf(fout, "%d ", tp.second + 1);
    }
    fprintf(fout, "\n");
}