模测成绩单

问题描述

模测结束了，小 L 拿到了一些形如 A 比 B 得分高 的信息，现在小 L 想要输出一份成绩排名表，使得排名表满足得到的信息，并且学号小的尽可能排在前面。

输入格式

第一行有两个整数，$n,m$ 表示有 $n$ 个同学，第 $i$ 个同学学号为 $i$ ，有 $m$ 条信息。
接下来有 $m$ 行，每行有两个整数 $A,B$ ，表示学号为 $A$ 的同学得分比学号为 $B$ 的同学得分高。
$1\le n,m\le 10^6$
$1\le A,B\le n$
数据保证有解

输出格式

输出一行 $n$ 个数，表示按照学号给出的排名。

样例输入

5 3
4 5
2 3
1 5

样例输出

1 2 3 4 5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int a, b;
int inDegree[1000005];

struct edge {
    int u, v, w, next;  // 出点、入点、边权、下一条边的编号
    bool operator<(const edge& e) const {
        return w < e.w;
    }
} e[2000005];

int tot = 0;                    // 当前边的总数
vector<int> head(1000005, -1);  // 储存每个节点的第一条边的编号，-1表示没有边

void addEdge(const int& u, const int& v, const int& w) {  // 加一条边
    e[tot].u = u, e[tot].v = v, e[tot].next = head[u], e[tot].w = w;
    head[u] = tot++;
}

void topoSort() {
    priority_queue<int, vector<int>, greater<int>> q;//用最小堆确保编号小的节点尽可能靠前
    for (int i = 1; i <= n; ++i)
        if (!inDegree[i])
            q.emplace(i);
    vector<int> ans;
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        ans.emplace_back(u);
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (--inDegree[v] == 0)
                q.emplace(v);
        }
    }
    if (int(ans.size()) == n)
        for (int i = 0; i < n; ++i)
            printf("%d ", ans[i]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &a, &b);
        inDegree[b]++;
        addEdge(a, b, 1);
    }
    topoSort();
    return 0;
}