[问题] is spanning tree wintercobra PTT批踢踢实业坊

楼主: wintercobra (wintercobra) 2012-04-29 23:01:50

请问一下
在测试 is_spanning_tree 这个功能时
会假定“给入的两个 graph 原本是完全一样的，只是少了一些边”吗？
也就是说，会不会给个完全不同的 graph ，或是偷拿走一些顶点，需要额外检验呢？
谢谢

作者: Usoul 2012-04-30 11:50:00

这一题可以说是独立题，跟read_graph中存入的图没有关系is_spanning_tree不用将input dot file存起来，只需要检查后输出 Yes/No 即可

楼主: wintercobra (wintercobra) 2012-04-30 13:56:00

了解，谢谢还有一个问题是，is_spanning_tree输出YES或NO是输出到stdout吗？

作者: Usoul 2012-04-30 23:29:00

是的。

作者: photonzero (邪心魔佛) 2012-05-02 18:21:00

所以说就是检查input dot file是否是tree吗

作者: Usoul 2012-05-02 19:27:00

是

作者: vincere (vin) 2012-05-05 10:19:00

想请问一下因为这篇关于is_spanning_tree的功能好像跟上课老师讲的有些不同记得老师好像说是要跟read进来的graph比所以想要确定一下不知我是否有误会意思？

作者: Usoul 2012-05-05 15:36:00

老师说明的是对的，在此更正一下：is_spanning_tree 要检查是否是原图的 spanning tree，之后再输出 Yes/No。所以不算是独立题所以除了检查是树之外，还要检查点都存在，且边是子集之前没有想清楚，所以回答得有问题，对不起 QQ"

作者: cjshine (花) 2012-05-05 17:02:00

请问一下检查边的时候需要检查它的label吗?

继续阅读