/ Vijos / 题库 /

相亲大会

相亲大会

时间限制:1秒  内存限制:256M


【题目描述】

  工会要举办一个相亲大会。已知报名参会的n位年轻人中,有些人曾经处过男女朋友。所以工会在决定最终的邀请名单中的任何一对男女都不能处过男女朋友。请计算这个相亲大会最多可以邀请多少人参加。

【输入格式】

  输入的第一行是 \(n\) 和 \(m\) 。其中 \(n\) 是报名参会的人数, \(m\) 是已处过男女朋友的对数。然后有 \(m\) 行,每行包括两个非负整数,表示这两个编号的年轻人曾经处过朋友。他们的编号从 \(0\) 号到 \(n - 1\) 号。

【输出格式】

 输出一个数字,即能够邀请的最多的人数。

【输入输出样例1】

 Input

8 6
0 2
2 3
3 5
1 4
1 6
3 1

 Output

5

【输入输出样例1】

 Input

20 5
5 2
4 3
18 17
0 11
13 3

 Output

16

【测试点性质】

  对于100%的数据,\(n \leq 1000\) , \(m \leq 2000\)。

【来源】

  Mr.he

信息

ID
3276
难度
(无)
分类
图结构 | 二分图二分图匹配 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
2
上传者