#36. 仙人掌上最大独立集

内存限制:512 MiB 时间限制:20000 ms 输入文件:set.in 输出文件:set.out
题目类型:传统 评测方式:文本比较
上传者: Shu_Yu_Mo

题目描述

给出一个仙人掌,求最大独立集.

输入格式

点数 n ,边数 m .

无向边: (u_i, v_i) .

输出格式

一行一个数字。表示答案。

样例

5 6
1 2
2 3
3 1
3 4
4 5
3 5
2

数据范围与提示

91\%, n \le 5\times 10^4

100\%, n \le 10^7

提示

对于 9\% 的数据,输入文件大小仅仅为 138 MB,建议使用较快的读入方法。 可以将传统快读中的 getchar() 函数改为如下:

#define getchar() (SB==TB&&(TB=(SB=BB)+fread(BB,1,1<<15,stdin),SB==TB)?EOF:*SB++)
char BB[1 << 16], *SB = BB, *TB = BB;

以应对较大量的读入。 UDP:这个 138 MB 的读入好像把系统 bug 炸出来了QAQ 可以下载后自行测试~。