← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

A6271 | 朋友分组

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有 $N$ 个人，从人 $1$ 到人 $N$。

给出 $M$ 条信息，每条信息表示「人 $A_i$ 和人 $B_i$ 是朋友」。同样的一对信息可能会被给出多次。

如果 $X$ 和 $Y$ 是朋友，且 $Y$ 和 $Z$ 是朋友，则 $X$ 和 $Z$ 也是朋友。除此之外，不能从这 $M$ 条信息推出的朋友关系一律视为不存在。

现在，「恶之 Welcome24ever」想把这 $N$ 个人分成若干组，使得对于每个人来说，同一组内没有他的朋友。

请你求出，最少需要分成多少组。

输入格式

从标准输入读入。

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$，表示人 $A_i$ 和人 $B_i$ 是朋友（可能会重复出现同一对人）。

$N\ M$

$A_1\ B_1$

$\vdots$

$A_M\ B_M$

输出格式

输出一个整数，表示最少需要分成的组数。

输入输出样例

输入 #1
5 3
1 2
3 4
5 1
输出 #1
3
输入 #2
4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4
输出 #2
4
输入 #3
10 4
3 1
4 1
5 9
2 6
输出 #3
3
C++ 编辑器
输入
输出