【蓝桥杯stema测试】收集宝石
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
聪聪在玩冒险岛游戏，为了召唤法力更强大的神龙，他必须尽可能收集更多的魔法宝石，每颗宝石都有不同的功效。不过在游戏里，几乎每一颗魔法宝石都会和另外一颗宝石相冲。相冲表示这两颗宝石不能同时拥有。例如，宝石A和宝石B 相冲，那么，你可以选择两颗宝石都不收集，也可以只收集宝石A 或者只收集宝石 B，但不能同时拥有宝石 A和宝石B现在给定了游戏里宝石的数量N(2≤N≤100)，宝石从1到N依次编号，并给出M对(2≤M≤2000)相冲的宝石编号，请帮聪聪计算出最多能够收集到多少颗宝石。
例如: N=6，M=8时，6颗宝石的编号分别为 1、2、3、4、5、6，其中有8对相冲的宝石，对应编号如下:
1 2
2 3
2 4
2 5
2 6
3 4
4 5
5 6
这表示宝石1和宝石2相冲，宝石2和宝石3,4,5都相冲，宝石3和宝石4相,冲宝石4和宝石5 相冲，宝石5 和宝石 6 相冲。
有三个方案收集到的宝石数量最多: (1 3 5)、(1 3 6)、(1 4 6)，这些方案里，最多收集到的宝石数量都是 3，所以程序输出 3。
输入格式
第一行输入两个正整数N和 M(2≤N≤100，2≤M≤2000)，分别表示游戏里的宝石数量和 M 对相冲的宝石，两个正整数之间用一个空格隔开。
接下来输入 M 行，每行两个正数，分别表示相冲的两颗宝石的编号，两个正整数之间用一个空格隔开
输出格式
输出一个整数，表示聪聪在游戏里最多能够收集到的宝石数量
样例 #1
样例输入 #1
6 8
1 2
2 3
2 4
2 5
2 6
3 4
4 5
5 6
样例输出 #1
3
蓝桥杯真题练习
- 状态
- 已结束
- 规则
- IOI
- 题目
- 19
- 开始于
- 2023-10-12 17:45
- 结束于
- 2023-10-16 21:45
- 持续时间
- 100 小时
- 主持人
-
刘老师 (图书管理员)
- 参赛人数
- 276
