题解

思路推导

把每个人看作顶点，把每条朋友信息看作无向边。由于朋友关系具有传递性，同一连通分量中的任意两个人最终都是朋友；不同连通分量之间则不是朋友。

一个连通分量中的人必须分到不同组，所以组数至少是最大连通分量大小。反过来，在每个连通分量内给顶点使用互不相同的组，并在不同分量之间重复使用这些组，就能用最大连通分量大小个组完成分配。

因此答案正是最大连通分量大小。

做法

在小规模下，可以用 Floyd 传递闭包求出任意两个人是否连通，再统计每行可达顶点数。

若每个连通分量都是完全图，则一个大小为 $c$ 的非孤立分量中每个顶点的唯一邻居数都是 $c-1$，答案为最大唯一度数加一；没有边时答案为 1。

一般情况下使用并查集。依次合并每条朋友信息的两个端点，维护每个根的集合大小，最后取最大值。

正确性证明

并查集在处理所有边后，两个顶点属于同一集合，当且仅当它们之间存在由给定朋友信息组成的路径，也就是朋友关系能够通过传递性推出。根节点记录的大小因此等于对应连通分量人数。

前述下界说明任一合法分组至少使用最大连通分量大小个组；按分量内部编号并在分量间复用组号又能达到该下界。因此并查集求得的最大集合大小就是最少组数。

复杂度分析

时间复杂度为 $O((N+M)\alpha(N))$，空间复杂度为 $O(N)$。