描述
H国有n个城市，城市与城市之间有m条单向道路，满足任何城市不能通过某条路径回到自己。
现在国王想给城市重新编号，令第i个城市的新的编号为a[i]，满足所有城市的新的编号都互不相同，并且编号为[1,n]之间的整数。国王认为一个编号方案是优美的当且仅当对于任意的两个城市i,j，如果i能够到达j，那么a[i]应当<a[j]。
优美的编号方案有很多种，国王希望使1号城市的编号尽可能小，在此前提下，使得2号城市的编号尽可能小...依此类推。
格式
输入格式
第一行读入n,m，表示n个城市，m条有向路径。
接下来读入m行，每行两个整数:x,y
表示第x个城市到第y个城市有一条有向路径。输出格式
输出一行:n个整数
第i个整数表示第i个城市的新编号a[i]，输出应保证是一个关于1到n的排列。样例1
样例输入1
5 44 11 35 32 5
样例输出1
2 3 5 1 4
限制
每个测试点1s
提示
30%的测试点满足：n <= 10, m <= 10
70%的测试点满足：n <= 1000, m <= 10000100%的测试点满足：n <= 100000, m <= 200000输入数据可能有重边，可能不连通，但保证是有向无环图。来源
Topcoder
/*逆拓扑+贪心，从后往前，先找编号最大的证明： 假设我们按逆拓扑排序的方法求出了一个拓扑序列（把得到的反序列正过来）,记为A。 假设最优解的拓扑序列是B。 从后往前比较AB,设在位置k,AB第一次出现不同。即A[k]!=B[k],A[p]=B[p]. 显然根据我们的贪心策略"每次取的是编号最大的"，有A[k]>B[k]. 那么我们在B中取寻找A[k],即找到B[p]=A[k]. 然后把B中B[p],B[p+1]...B[k]这一段拿出来,记为序列C。 因为B[p]=A[k] , 把B[p]换成A[k],C=A[k],B[p+1]....B[k]. 很显然在C中A[k]不是最小的,因为至少B[k]比它小。 假设C中最小的是B[q],那么我们可以构造出一个序列D. D=B[p+1],B[p+2]...B[q],A[k],B[q+1]...B[k]. (实质就是把A[k]移到B[q]的后面） 显然这个序列会比序列C更优,因为B[q]的名次靠前了一名。 那么如果把C换成D会更优,与B是最优解矛盾。 那么怎么知道序列D一定是合法的呢？因为如果A[k]恰好是B[p+1]的前驱,那么就不能把A[k]移走。 所以我们回到序列A,序列A中A[k]是AB序列从右往左第一个不同的元素,那么在A中,B[p+1]肯定是在A[k]前面的,所以A[k]不可能是B[p+1]的前驱。 综上,我们得到的答案就是最优解。如果不理解，按照样例举个例子 4 -> 1 -> 3 <-5 <-2; 如果贪心，每次找入度为0的点，若有多点，找编号小的点： 第一次找到 2; 第二次找到 4; 第三次找到 1; 第四次找到 5; 第五次找到 3； 这显然是错误的： 按照上面方法 逆拓扑，从后往前，先找编号最大的 1ci find 3, 3 number 5; 2ci find 5, 5 number 4; 3ci find 2, 2 number 3; 4ci fine 1, 1 number 2; 5ci fine 4, 4 number 1; fit answer;*/#include#include #include #include using namespace std;const int maxn = 100000 + 10;const int maxm = 200000 + 10;int n, m;int cloc;int cnt[maxn], id[maxn];vector G[maxn];priority_queue Q;int main () { scanf("%d%d",&n,&m); while (m--) { int u, v; scanf("%d%d", &u, &v); u--; v--; cnt[u]++; G[v].push_back(u); } for (int i = 0; i < n; i++) if (!cnt[i]) Q.push(i); cloc = n; while (!Q.empty()) { int u = Q.top(); Q.pop(); id[u] = cloc--; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; cnt[v]--; if (cnt[v] == 0) Q.push(v); } } for (int i = 0; i < n; i++) printf("%d ", id[i]); return 0;}