C++14 解法, 执行用时: 47ms, 内存消耗: 8420KB, 提交时间: 2020-07-28

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
   
vector<int> solve(vector<vector<int>> &adj, vector<int> &in, int n)
{
    priority_queue<int> q;
    vector<int> ret(n+1);
    int cnt = n;
       
    for (int i=1; i<=n; i++)
        if (in[i]==0)
            q.push(i);
       
    while (!q.empty())
    {
        int t = q.top();
        q.pop();
        ret[t] = cnt--;
        for (int i=0; i<adj[t].size(); i++)
            if (--in[adj[t][i]]==0)
                q.push(adj[t][i]);
    }
       
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<vector<int>> adj(n+1);
    vector<int> in(n+1, 0);
       
    for (int i=0; i<k; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
        in[u]++;
    }
       
    vector<int> ret = solve(adj, in, n);
    for (int i=1; i<=n; i++)
        cout << ret[i] << " ";
    return 0;
}

C++ 解法, 执行用时: 49ms, 内存消耗: 7196KB, 提交时间: 2020-10-29

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
  
vector<int> solve(vector<vector<int>> &adj, vector<int> &in, int n)
{
    priority_queue<int> q;
    vector<int> ret(n+1);
    int cnt = n;
      
    for (int i=1; i<=n; i++)
        if (in[i]==0)
            q.push(i);
      
    while (!q.empty())
    {
        int t = q.top();
        q.pop();
        ret[t] = cnt--;
        for (int i=0; i<adj[t].size(); i++)
            if (--in[adj[t][i]]==0)
                q.push(adj[t][i]);
    }
      
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<vector<int>> adj(n+1);
    vector<int> in(n+1, 0);
      
    for (int i=0; i<k; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
        in[u]++;
    }
      
    vector<int> ret = solve(adj, in, n);
    for (int i=1; i<=n; i++)
        cout << ret[i] << " ";
    return 0;
}