《算法竞赛进阶指南》有毛病!
  • 板块学术版
  • 楼主STUDENT00
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/10/2 11:05
  • 上次更新2023/11/2 16:37:07
查看原帖
《算法竞赛进阶指南》有毛病!
658786
STUDENT00楼主2023/10/2 11:05

看到 P443P_{443},例题Knights of the Round Table引理1:若两个骑士属于两个不同的“点双连通分量”,则他们不可能一起出席会议。

这是错误的!反例:

考虑有9个点,11条边如下:

1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 3
5 8
8 9
9 5

此时共有3个点双连通分量:

1.1 2 3
2.3 4 5 6 7
3.5 8 9

而1号点双的3号点与3号点双的5号点可以一起参加会议,即3 4 5 6 7这5人参加。

2023/10/2 11:05
加载中...