社区讨论

欧拉路一定需要验证奇点之外点的出入度吗?

P7771【模板】欧拉路径参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo8rhaab
此快照首次捕获于
2023/10/27 23:21
2 年前
此快照最后确认于
2023/10/27 23:21
2 年前
查看原帖
如题,蒟蒻今天写相关题目时只判断了奇点个数,没有判断其他点出入度是否相等,结果过了。于是写了一发板子不判断其他点仍然过了(复健中,代码略丑见谅)。
蒟蒻很疑惑:如果定义出奇点为出度恰比入度大一的点,入奇点为入度恰比出度大一的点。弱连通图中,不存在或仅存在一对出奇点、入奇点是否是这个图存在欧拉路的充分条件。
不知道是题目数据强度问题还是确有这样结论,蒟蒻一时间想不出反例,还请各位巨佬解答。如果成立有证明思路那是最好的。

回复

3 条回复,欢迎继续交流。

正在加载回复...