首页 > 试题广场 >

拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列，

[填空题]
拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列，使得图中任意一对 顶点 u 和 v，若 ∈E(G)，则 u 在线性序列中出现在 v 之前，这样的线性序列成为拓 扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数 为 1。

查看正确选项
添加回答
Venμs头像 Venμs
先考虑前 7 个点，显然 1 和 6 是必然放在最前面和最后面的，然后考虑另外 5 个点，5 任意放，3 在 2 之后，4 和 7 在 3 之后，那么就有 1 2 3 4 7 6 和 1 2 3 7 4 6 两种情况，在里面插入 5 则有 12 种情况，然后考虑 8 和 9，9 要在 8 后面，则对于每一种情况有 1 + 2 + ... + 8 = 36 种情况，12 * 36 = 432。
发表于 2019-10-15 14:16:44 回复(0)
文雨淋头像 文雨淋
1、首先考虑8->9这两个点，根据拓扑排序规则，8,9两个点可以在序列的任意位置，1->7一共有8个空，又8要在9前，所以不计算8和9之间的相对排列顺序产生的答案。我们可以吧8和9绑在一起，也可以把他们分开，这样产生对答案的贡献有C(1,8)+C(2,8)。
2、模拟拓扑排序的过程，当把1删掉后，5可以插在2->6之间(6个空)，这样对答案的贡献有C(1,6)。
3、当把3删掉后，4可以放在7的两边，对答案的贡献有C(1,2)。
4、根据乘法原理统计答案 ans=( (C(1,8)+C(2,8) ) * C(1,6) * (1,2)=432
发表于 2019-10-13 21:28:21 回复(0)
提交观点

问题信息

提高 C++ Pascal 图论 问题求解
来自：NOIP2009初赛普及组
上传者：牛客309901号
难度：
2条回答 6213浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号