Skip to content

14141: 【原4141】knight

题目

题目描述

author: Sakiko 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4141

题目描述

亚瑟王要在圆桌上召开骑士会议,为了不引发骑士之间的冲突,并且能够让会议的议题有令人满意的结果,于是他鬼畜地决定每次开会前都必须对出席会议的骑士有如下要求: 1.相互憎恨的两个骑士不能坐在直接相邻的2个位置; 2.出席会议的骑士数必须是奇数,这是为了让投票表决议题时都能有结果。 3.一次圆桌会议需要3个或3个以上的骑士参与,并且排成一个环。 如果出现有某些骑士无法出席所有会议(例如这个骑士憎恨所有的其他骑士),则亚瑟王为了世界和平会强制把他剔除出骑士团。 现在给定准备去开会的骑士数\(n\),再给出\(m\)对憎恨对(表示某2个骑士之间是互相憎恨的),问亚瑟王至少要剔除多少个骑士才能顺利召开会议?

输入数据

第一行两个数\(n,m\)。 接下来m行,每行两个数\(x,y\),表示\(x\)号骑士和\(y\)号骑士相互憎恨。

输出数据

一个数\(ans\),表示至少需要剔除多少个骑士。

输入样例

5 4
1 2
2 3
3 4
1 4

输出样例

0

数据规模

对于30%的数据,\(n<=30\) 对于50%的数据,\(n<=50\) 对于100%的数据,\(n<=1000\)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!