题解

题面描述

在音乐服务中，为了提升用户体验，需要推荐给用户的歌单之间不包含相同的歌曲。具体来说，给定 N 个歌单和 M 条歌单重复记录（即两两歌单之间存在相同的歌曲），要求通过合并歌单的方式，使得合并后的每个歌单内部不含有相同的歌曲。目标是找到合并后的最小歌单数量。

问题转化

这个问题可以转化为图论中的图着色问题：

题目内容

假设你是音乐服务的开发者，为了提高用户体验需要解决推荐歌单的同质化问题，保证推荐给用户的所有歌单不包含相同歌曲的。

给定一个包含 $N$ 个歌单和 $M$ 条歌单重复记录，每个歌单用一个从 $1$ 到 $N$ 的整数编号，歌单重复记录包含两个歌单的 $ID$ ，表示两个歌单有相同的歌曲。

你的任务是对歌单进行合并，找出合并后的最小歌单数量，合并的歌单中不能有相同的歌曲。

输入描述

第一行包含两个整数 $N$ 和 $M$，分别表示歌单的数量和有相同歌曲的歌单记录数。

接下来 $M$ 行，每行包含两个整数编号 $X$ 和 $Y$，表示编号为 $X$ 和 $Y$ 的歌单有相同的歌曲。

1.输入不会出现相同歌单，例如不会出现"$1$ $1$ ”这种输入

2.输入不会出现多条重复的记录，例如"$1$ $2$"不会出现多次

3.最大歌单数量不超过 $100$

4.歌单有重复歌曲记录数 $M$ 不会超过 $1024$

5.歌单 $1$ 和 $2$ 有相同歌曲，歌单 $2$ 和 $3$ 有相同歌曲，歌单 $1$ 和 $3$ 不一定包含相同歌曲

输出描述

输出一个整数，表示合并后的最小歌单数

样例1

输入

5 6
1 2
1 3
1 4
2 3
2 5
4 5

输出

3

说明

输入：

有 $5$ 个歌单，歌单编码从 $1$ 到 $5$ ;有 $6$ 条重复歌单记录，每一条记录包含了歌单的编码。

$1$ 和 $2$ 有相同歌曲; $1$ 和 $3$ 有相同歌曲; $1$ 和 $4$ 有相同歌曲; $2$ 和 $3$ 有相同歌曲; $2$ 和 $5$ 有相同歌曲; $4$ 和 $5$ 有相同歌曲。

输出：

输出合并后最小歌单数为 $3$ ，合并后的 $3$ 个歌单内没有相同歌曲

$1$ 和 $5$ 一组; $3$ 和 $4$ 一组; $2$一组(或者 $1$ 和 $5$ 一组; $2$ 和 $4$ 一组; $3$ 一组)，合并组合可能有多种，只需要输出合并后的最小数。

样例2

输入

4 3
1 2
1 3
1 4

输出

2

说明

$2/3/4$ 一组，没有相同歌曲; $1$ 一组。