1424-部落护卫队


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:2 提交数:2 难度:4


题目描述:

在原始部落中,由于食物缺乏,部落居民经常因为争夺猎物发生冲突,几乎每个居民都有自己的仇敌。部落酋长为了组织一支保卫部落的卫队,希望从居民中选出最多的居民加入卫队,并保证卫队中任何两个人都不是仇敌。假设已给定部落中居民间的仇敌关系图,编程计算构建部落护卫队的最佳方案。

输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据第一行输入部落人数n和人与人之间的关系数c(1<=n<=100,1<=c<=10000)。
接下来有c行,每行输入两个数,代表有友好关系的两个人序号u,v(1<=u,v<=100)。

输出描述:

对于每一组输入,输出部落护卫队的最大人数。
每组的输出占一行。

样例输入:

2
5 8
1 2
1 3
1 4
1 5
2 3
3 4
3 5
4 5
4 5
1 2
1 4
2 3
2 4
3 4

样例输出:

4
3

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!