Educational Codeforces Round 25 E. Minimal Labels

题目链接：​​Minimal Labels​​

题目大意：给你一个DAG，n个点，m条边，现在要求你用1-n这n个数对每个点标记，如果存在一条从u到v的边，那么v的标记需要比u大，结果输出1-n每个点的标记，并且要求字典序最小

题目思路：我们可以很轻松的想到我们首先要从出度为0的点开始标记，因为出度为零，不出边，那么让他最大当然是没问题的，然后就是因为要字典序最小，所以出度为零的好几个，肯定要让值最大的数标记最大，然后这个点相当于扔掉了，跟他相连的点出度减一，那么我们可以用优先队列来存出度为零的值，题目就解决了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 1e5+10;

int main(){
int n,m,u,v;
vector<int>vec[maxn];
int out[maxn],res[maxn];
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d",&u,&v);
vec[v].push_back(u);out[u]++;
}
priority_queue<int>pq;
for(int i = 1;i <= n;i++){
if(!out[i]) pq.push(i);
}
int t = n;
while(!pq.empty()){
int now = pq.top();
pq.pop();
res[now] = t--;
for(int i = 0;i < vec[now].size();i++){
out[vec[now][i]]--;
if(!out[vec[now][i]]) pq.push(vec[now][i]);
}
}
for(int i = 1;i <= n;i++)
printf("%d ",res[i]);
puts("");
return 0;
}