3445：【2024年8月】7级算法等考第2题 部落联盟
文件提交：无需freopen
内存限制：256 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：2
解决：0
题目描述
## Description
在一片原始土地上分布着n个部落，编号分别为1到n，这些部落为了争夺资源经常发生冲突，有些部落之间互相视对方为仇敌。有一天，掌管这片土地的大长老想要从这n个部落中挑选一些部落，成立部落联盟，但是要保证联盟中任意两个部落都不是仇敌关系，请问大长老最多能挑选出多少个部落组成联盟？
## Input Format
第一行包含两个整数n，m，分别表示部落的数量以及仇敌关系的数量，整数之间以一个空格隔开；
接下来m行，每行包含两个整数x，y，表示部落x和部落y之间是仇敌关系，整数之间以一个空格隔开。
数据范围
测试点1~10：1≤n≤100，1≤m≤1000，1≤x，y≤n。
## Output Format
一个整数，表示大长老最多能挑选出多少个部落组成联盟。
```input1
7 10
1 2
1 4
2 4
2 3
2 5
2 6
3 5
3 6
4 5
5 6
```
```output1
3
```
## Hint
包含1号部落在内的最多部落数量的联盟有（1，3，7）或（1，5，7）或（1，6，7）；
包含2号部落在内的最多部落数量的联盟有（2，7）；
包含3号部落在内的最多部落数量的联盟有（1，3，7）或（3，4，7）；
包含4号部落在内的最多部落数量的联盟有（3，4，7）或（4，6，7）；
包含5号部落在内的最多部落数量的联盟有（1，5，7）；
包含6号部落在内的最多部落数量的联盟有（1，6，7）或（4，6，7）；
包含7号部落在内的最多部落数量的联盟有（1，3，7）或（1，5，7）或（1，6，7）或（2，7）或（3，4，7）或（4，6，7）；
因此，最多能挑选出3个部落组成联盟。