题目详情题解（0）讨论（0）提交记录（0）

AT_abc177_d.[ABC177D] Friends

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 NN 个人，从人 11 到人 NN。

给出 MM 条信息，每条信息表示“人 AiA_i 和人 BiB_i 是朋友”。同样的信息可能会被给出多次。

如果 XX 和 YY 是朋友，且 YY 和 ZZ 是朋友，则 XX 和 ZZ 也是朋友。此外，不能从这 MM 条信息推出的朋友关系不存在。

“恶之高桥君”想把这 NN 个人分成若干组，使得对于每个人来说，“同一组内没有朋友”。

请问最少需要分成多少组？

输入格式

输入从标准输入按以下格式给出。

NN MM
A1A_1 B1B_1
⋮\vdots
AMA_M BMB_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

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 0≤M≤2×1050 \leq M \leq 2 \times 10^5
  • 1≤Ai,Bi≤N1 \leq A_i, B_i \leq N
  • Ai≠BiA_i \neq B_i

样例解释 1

例如，将人分为 {1,3}\{1,3\}、{2,4}\{2,4\}、{5}\{5\} 这 33 个组，可以满足要求。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页