关于拓扑排序
  • 板块学术版
  • 楼主No_Rest
  • 当前回复1
  • 已保存回复2
  • 发布时间2024/6/10 23:06
  • 上次更新2024/6/11 15:02:59
查看原帖
关于拓扑排序
550821
No_Rest楼主2024/6/10 23:06

对于一个有向有环图,记拓扑排序后遍历到的节点数为 cnt1cnt_1。

若我们将这个图内所有边全部变反(如原来 u→vu \to v,现在 v→uv \to u),记此时拓扑排序后遍历到的节点数为 cnt2cnt_2。

试问 cnt1cnt_1 和 cnt2cnt_2(可能还有总节点数 nn,所有环包含的节点数等)之间有没有什么关系(大概没有)。

问题可能比较蠢。

2024/6/10 23:06
加载中...