C++ 解法, 执行用时: 2ms, 内存消耗: 288KB, 提交时间: 2021-07-26

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main(void) {
  int n, e;
  cin >> n >> e;
  vector<int> weights(n + 1);
  
  int seq, w;
  for (int i = 0; i < n; ++i) {
    cin >> seq >> w;
    weights[seq] = w;
  }
  
  int u, v;
  vector<vector<int>> g(n + 1);
  vector<int> indegrees(n + 1, 0);
  for (int i = 0; i < e; ++i) {
    cin >> u >> v;
    g[u].emplace_back(v);
    ++indegrees[v];
  }
  
  priority_queue<pair<int, int>> q; // maximum heap
  for (int u = 1; u <= n; ++u) 
    if (!indegrees[u]) q.emplace(weights[u], u);
  
  while (not q.empty()) {
    const auto [weight, curr] = q.top(); q.pop();
    cout << curr << ' ';
    for (const int nxt : g[curr])
      if (!--indegrees[nxt]) q.emplace(weights[nxt], nxt);
  }
  
  return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 300KB, 提交时间: 2022-01-23

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, vector<int>> adj;

vector<int> w;

bool cmp(int o1, int o2)
{
    return w[o1] > w[o2];
}

int main()
{
    int n, e; //节点数 和 边数
    scanf("%d %d", &n, &e);
    vector<int> indegree(n + 1, 0); //每个节点的入度
    w = vector<int>(n + 1, 0);      //每个节点的权重
    for (int i = 1; i <= n; i++)
    {
        int vex, weight;
        scanf("%d %d", &vex, &weight);
        w[vex] = weight;
    }
    for (int i = 1; i <= e; i++)
    {
        int vex1, vex2;
        scanf("%d %d", &vex1, &vex2);
        indegree[vex2]++; //入度
        adj[vex1].push_back(vex2);
    }
    for (auto it = adj.begin(); it != adj.end(); it++)
    {
        sort(it->second.begin(), it->second.end(), cmp);
    }
    vector<int> a;
    queue<int> queue;
    for (int i = 1; i <= n; i++)
    {
        if (indegree[i] == 0)
        {
            a.push_back(i);
        }
    }
    sort(a.begin(), a.end(), cmp);
    for (int i = 0; i < a.size(); i++)
        queue.push(a[i]);
    while (queue.empty() == false)
    {
        int t = queue.front();
        queue.pop();
        printf("%d ", t);
        a.clear();
        for (int i = 0; i < adj[t].size(); i++)
        {
            if (--indegree[adj[t][i]] == 0)
            {
                a.push_back(adj[t][i]);
            }
        }
        sort(a.begin(), a.end(), cmp);
        for (int i = 0; i < a.size(); i++)
            queue.push(a[i]);
    }
    //system("pause");
    return 0;
}