Codeforces 825E Minimal Labels - 拓扑排序+思维
E. MinimalLabels
time limit pertest 1 second
memory limit pertest 256 megabytes
input standard input
output standard output
You are given a directed acyclic graphwith n verticesand m edges.There are no self-loops or multiple edges between any pair of vertices. Graphcan be disconnected.
You should assign labels to all vertices in such a waythat:
· Labels form a valid permutation of length n — aninteger sequence such that each integer from 1 to n appearsexactly once in it.
· If there exists an edge from vertex v tovertex u then labelv should besmaller than labelu.
· Permutation should be lexicographically smallest amongall suitable.
Find such sequence of labels to satisfy all the conditions.
Input
The first line contains two integer numbers n, m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105).
Next m lines contain two integernumbers v and u (1 ≤ v, u ≤ n, v ≠ u) — edges of thegraph. Edges are directed, graph doesn't contain loops or multiple edges.
Output
Print n numbers — lexicographicallysmallest correct permutation of labels of vertices.
Examples
input
3 3
1 2
1 3
3 2
output
1 3 2
input
4 5
3 1
4 1
2 3
3 4
2 4
output
4 1 2 3
input
5 4
3 1
2 1
2 3
4 5
output
3 1 2 4 5
我觉得是拓扑排序+一点点思维。
题意：
题目意思是说：给你一个DAG（无环有向图）且没有重边，图中顶点的编号从1到n，现在要对顶点进行重新编号，满足几个条件
1如果有一条从V到U的边，那么V的编号小于U的编号
2如果有多组解，输出最后结果字典序最小的那组解。
分析：
拿到题目简单分析下，把题目分析下以后，可以用拓扑排序做。
开始看第二个样例看了好久，都不明白为什么序列是这个。
后来研究了下（没在题目中找到具体句子），才知道是题目要求输出的是编号以后原序列在新编号中的位置。
比如说第二个样例，拓扑排序以后是2 3 4 1，但输出的是4 1 2 3；
因为原来的1在新序列中处于第四个位置，原来的2在新序列中处于第一个位置，以此类推。
解题：
因为正向拓扑排序只能得到一个相对关系，和我们最后要输出的序列还有很大的差距。
如果在花费时间在调整输出序列，必然超出题目给的时限。
现在我们反其道行之，反向建边。这样建边以后，原来第一个找到的点会变成最后一个找到的点，这样逆序编号下去，就能得到符合题意的输出序列。
但是，题目要求输出的序列字典序最小（当然，没有这个条件时，我们也要考虑当有两个点入度都为0时该标记哪个点的问题）
因为我们是反向标记，所以标记的数字越来越小，为了使得最后输出的序列字典序最小，那么我们要把小的标记数字留给原序列中靠前的点（即是每次选择原序列中数字大的点标记）
例如，此时原序列3 和6都是入度为0的点，现在标记数字为2，那么我们为保证字典序最小，我们把2给6，把1给3，输出序列就变成1 2,（反过来就变成2 1）
这个可以用个优先队列实现
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<list>
#include<queue>
using namespace std;
list<int> l[100005];
int n,m;
int indegree[100005];
int ans[100005];
void topsort()
{
int i,k;
int cnt,top;
priority_queue<int> que;//默认升序排列
for(i=1;i<=n;i++)
{
if(indegree[i]==0)
que.push(i);
}
i=n;
while(que.size())
{
k=que.top();
ans[k]=i;
i--;
que.pop();
cnt++;
while(!l[k].empty())
{
top=l[k ].front();
l[k ].pop_front();
indegree[top]--;
if(indegree[top]==0)
que.push(top);
}
}
}
int main()
{
int i,a,b;
scanf("%d%d",&n,&m);
memset(indegree,0,sizeof indegree);
memset(ans,0,sizeof ans);
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
l[b].push_back(a);
indegree[a]++;
}
topsort();
for(i=1;i<=n;i++)
if(i!=n)
printf("%d ",ans[i]);
else
printf("%d\n",ans[i]);
}
自愧不如