[POI2006]Zos
时间限制：50s 空间限制：259MB
题目描述
给出一个N个点M条边的无向图G，定义图G的一个独立集为一个顶点集合V’，满足V’∈V，并且对于任何a∈V’且b∈V’的a和b，不存在(a,b)∈E。 问是否存在顶点个数不小于K的独立集，如果存在，找出顶点个数最多的独立集。
输入格式
第一行两个正整数N (2 <= n="" <="1,000,000)、K" (n-10="" (1="" b="" a="" ≠="" b)，表示一条边。（注意同样的边可能多次出现）="" p="">
输出格式
如果不存在顶点个数不小于K的独立集，就输出NIE，否则输出最大独立集的顶点个数。
样例输入
9 4 12 9 6 4 6 7 9 1 2 2 1 9 7 7 6 4 5 7 8 8 9 3 4 4 3
样例输出
5
提示
最大独立集为{1, 3, 5, 6, 8}。 ================================== 鸣谢Oimaster
题目来源
没有写明来源