Toggle navigation
HUSTOJ
F.A.Qs
Web Board
ProblemSet
Source/Category
Status
Ranklist
Contest
Login
Language
中文
ئۇيغۇرچە
English
فارسی
ไทย
한국어
Problem1129--最大独立集2(一般图)(元问题byscy)
1129: 最大独立集2(一般图)(元问题byscy)
Time Limit:
1
Sec
Memory Limit:
128 MB
Submit:
1
Solved:
1
[
Status
] [
Submit
] [Creator:
]
Description
【题意】
就一个集合,集合里有n个点,
有k条边。
问题:选出某些点组成一个集合,使得集合中的任意两点之间没有边相连,问这个集合最多可以包含多少个点?
【输入格式】
数据第一行三个整数n(1 ≤ n,≤ 10000) and k (0 ≤ k ≤ n × n 且 k<= 10^6),
下来k行,每行两个整数 x and y (1 ≤ x,y ≤ n), 表示一条边的两个端点。
【输出格式】
输出一行,一个整数,即集合最多可以包含的点的个数。
【样例1输入】
3 2
1 2
2 3
【样例1输出】
2
【样例2输入】
4 5
1 2
1 3
2 3
3 1
4 1
【样例2输出】
2
【样例3输入】
6 10
1 2
1 3
1 4
1 5
2 1
3 1
3 5
4 1
4 5
5 1
【样例3输出】
4
Source/Category