来源公众号：吴师兄学算法 ID：CXYxiaowu

最近先给大家更新一些华为笔试真题。

题目描述

小慕是一名音乐服务开发者，为了提高用户体验，他需要解决推荐歌单的同质化问题。具体来说，他需要确保推荐给用户的歌单中不包含相同的歌曲。

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

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

输入格式

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

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

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

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

最大歌单数量不超过 100。

歌单有重复歌曲记录数 M 不会超过 1024。

如果歌单 1 和 2 有相同歌曲，歌单 2 和 3 有相同歌曲，歌单 1 和 3 不一定包含相同歌曲。

输出格式

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

样例

输入样例 1

5 61 21 31 42 32 54 5

输出样例 1

提示 1

有 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 31 21 31 4

输出样例 2

提示 2

歌单 2、3、4 一组，没有相同歌曲；

歌单 1 一组。

题目解析

对于用例1，其图如下：

由于2的度数最大，因此选择1，染色成0.

剩余的节点，由于2的度数最大，因此选择2，染色成1.

剩余的节点，由于3的度数最大，在此之上，其饱和度目前也是最大，因此选择3，染色成2.

剩余的节点，由于4的度数最大，因此选择4，染色成1.

剩余的节点只剩下5，染色成0.

理解题目

在音乐推荐系统中，同质化的歌单会降低用户体验，因此需要对相似的歌单进行合并，确保最终的歌单列表中没有重复的歌曲。题目要求我们找到合并后的最小歌单数量。给定 N 个歌单以及 M 条重复歌曲记录，每条记录表明两个歌单之间有相同的歌曲，因此它们不能同时出现在同一个合并歌单中。

换句话说，题目可以抽象为一个图的着色问题。其中：

每个歌单可以看作图中的一个节点。
如果两个歌单有相同的歌曲，则它们之间存在一条无向边。
目标是找到最少的颜色（分组），使得相邻的节点颜色不同，即使得每个独立分组内没有相同歌曲的歌单。

使用算法

这道题的本质是图的着色问题，目标是求出图的最小染色数（Chromatic Number）。该题使用了Dsatur（Degree of Saturation）算法来求解最小着色数。DSATUR算法是一种启发式的图着色方法，它通过选择具有最大“饱和度”的节点来优化着色过程。节点的饱和度指的是它已经着色的邻居节点的数量，饱和度较高的节点通常是着色顺序中较为优先的节点。

具体来说，Dsatur的基本思想是：

每次选择当前饱和度最大的节点来着色。
如果有多个节点具有相同的饱和度，则选择度数最大的节点，即与更多节点相连的节点。
这样做的原因是通过优先给“冲突”更多的节点着色，可以有效减少后续分配设备时的冲突。

最终的结果就是最小的合并后歌单数量，即整个图染色所需的最小颜色数。

实现

数据读取与存储

读取 N 和 M，分别代表歌单数量和重复记录数。
使用邻接表（Adjacency List）存储歌曲重复关系，即 g[x].append(y) 和 g[y].append(x)。

辅助数据结构

colors 数组：记录每个歌单的分组编号，初始值设为 -1（表示未分配）。
deg 数组：记录每个歌单的连接度（即有多少个重复关系）。
used 数组：用于存储每个歌单的相邻歌单已经使用过的分组编号。

贪心算法

get_node()：从未分配分组的歌单中选择最优节点，优先选择已使用分组数较少但连接度高的歌单。
get_col(v)：获取节点 v 可以使用的最小分组编号（从 0 开始）。
依次为所有歌单分配分组，并确保相邻歌单的分组不同。

最终结果

由于颜色编号从 0 开始，因此最终的最小合并歌单数为 ans + 1。

代码

Python

# 读取歌单数量 N 和歌单重复记录数 Mn, m = map(int, input().split())# 使用邻接表 g 来存储有相同歌曲的歌单之间的关系g = [[] for _ in range(n)]# 读取 M 条歌单重复记录，并构建邻接表for _ in range(m): x, y = map(int, input().split()) x -= 1# 将歌单编号从 1 调整到 0，方便数组索引 y -= 1# 同样将编号调整为 0-based g[x].append(y) # 记录双向关系 g[y].append(x)# 颜色数组 colors 记录每个歌单被分配到的分组编号，-1 表示尚未分配colors = [-1for _ in range(n)]# 记录每个歌单的连接度（即与多少个歌单存在相同歌曲）deg = [len(g[i]) for i in range(n)]# used 数组存储每个歌单的相邻歌单已经使用过的分组编号used = [set() for _ in range(n)]# 获取一个尚未分配分组的歌单（优先选择已用分组数少且连接度高的）def get_node(): tp = [-1, -1] # 记录最优候选歌单的 [已用分组数, 连接度] vertex = -1# 记录符合条件的歌单编号 for v in range(n): t = [len(used[v]), deg[v]] # 计算当前歌单的 [已用分组数, 连接度] if colors[v] == -1and t > tp: # 选择尚未分配且更优的歌单 tp = t vertex = v return vertex# 获取歌单 v 可使用的最小分组编号def get_col(v): val = 0# 从 0 开始寻找可用的分组编号 while val in used[v]: # 如果该编号已被相邻歌单使用，则尝试下一个 val += 1 return val# 记录最终需要的最小分组数量ans = -1# 依次为所有歌单分配分组for _ in range(n): u = get_node() # 选取一个尚未分配分组的歌单 if u == -1: # 如果所有歌单都已分配，则退出循环 break col = get_col(u) # 获取当前歌单可用的最小分组编号 colors[u] = col # 为该歌单分配分组 ans = max(ans, col) # 记录所需的最大分组编号 # 遍历当前歌单的所有相邻歌单，更新它们的已使用分组集合 for v in g[u]: if colors[v] == -1: # 如果该相邻歌单尚未分配分组 used[v].add(col) # 标记该分组已经被使用# 由于分组编号是从 0 开始的，所以最终答案需要加 1print(ans + 1)

C++

#include <iostream>#include <vector>#include <set>#include <algorithm>usingnamespacestd;// 全局变量定义int n, m; // 歌单数量 n 和歌单重复记录数 mvector<vector<int>> g; // 邻接表 g，用于记录哪些歌单有相同歌曲vector<int> colors; // 记录每个歌单的分组编号，-1 表示未分组vector<int> deg; // 记录每个歌单的连接度（即它与多少个歌单有相同歌曲）vector<set<int>> used; // 记录每个歌单的邻接歌单已使用的分组编号// 获取一个尚未分组的歌单编号int get_node() { vector<int> tp = {-1, -1}; // 记录当前候选歌单的度数和已用分组数 int vertex = -1; // 记录符合条件的歌单编号 for (int v = 0; v < n; v++) { vector<int> t = {used[v].size(), deg[v]}; if (colors[v] == -1 && t > tp) { // 选择一个邻接歌单多、已用分组少的歌单 tp = t; vertex = v; } } return vertex;}// 获取歌单 v 可以使用的最小分组编号int get_col(int v) { int val = 0; while (used[v].count(val)) { // 如果该编号已被邻接歌单使用，则尝试下一个编号 val++; } return val;}int main() { cin >> n >> m; // 读取歌单数量和重复记录数 g.resize(n); // 初始化邻接表 // 读取重复记录，并建立邻接表 for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; x--, y--; // 歌单编号调整为 0 开始 g[x].push_back(y); g[y].push_back(x); } colors.resize(n, -1); // 初始化分组编号数组 deg.resize(n); // 初始化连接度数组 used.resize(n); // 初始化已用分组记录 for (int i = 0; i < n; i++) { deg[i] = g[i].size(); // 计算每个歌单的连接度 } int ans = -1; // 记录最大分组编号 // 进行分组 for (int i = 0; i < n; i++) { int u = get_node(); // 获取一个未分组的歌单 if (u == -1) break; int col = get_col(u); // 获取可以使用的最小分组编号 colors[u] = col; ans = max(ans, col); // 记录最大分组编号 // 将该歌单的分组编号记录到其邻接歌单的已使用分组集合中 for (int v : g[u]) { if (colors[v] == -1) { used[v].insert(col); } } } cout << ans + 1 << endl; // 输出最小合并歌单数量 return0;}

Java

import java.util.*;publicclass Main { // 全局变量定义 staticint n, m; // 歌单数量 n 和歌单重复记录数 m static ArrayList<Integer>[] g; // 邻接表 g，记录哪些歌单有相同歌曲 staticint[] colors; // 记录每个歌单的分组编号，-1 表示未分组 staticint[] deg; // 记录每个歌单的连接度 static HashSet<Integer>[] used; // 记录每个歌单的邻接歌单已使用的分组编号 // 获取一个尚未分组的歌单编号 static int getNode() { int[] tp = {-1, -1}; // 记录当前候选歌单的度数和已用分组数 int vertex = -1; for (int v = 0; v < n; v++) { int[] t = {used[v].size(), deg[v]}; if (colors[v] == -1 && compareArrays(t, tp) > 0) { // 选择邻接歌单多、已用分组少的歌单 tp = t; vertex = v; } } return vertex; } // 获取歌单 v 可以使用的最小分组编号 static int getCol(int v) { int val = 0; while (used[v].contains(val)) { val++; // 如果该编号已被邻接歌单使用，则尝试下一个编号 } return val; } // 比较两个数组的大小 static int compareArrays(int[] t, int[] tp) { for (int i = 0; i < t.length; i++) { if (t[i] > tp[i]) return1; if (t[i] < tp[i]) return -1; } return0; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); // 读取歌单数量 m = sc.nextInt(); // 读取重复记录数 g = new ArrayList[n]; for (int i = 0; i < n; i++) { g[i] = new ArrayList<>(); } for (int i = 0; i < m; i++) { int x = sc.nextInt() - 1; int y = sc.nextInt() - 1; g[x].add(y); g[y].add(x); } colors = newint[n]; Arrays.fill(colors, -1); deg = newint[n]; used = new HashSet[n]; for (int i = 0; i < n; i++) { deg[i] = g[i].size(); used[i] = new HashSet<>(); } int ans = -1; for (int i = 0; i < n; i++) { int u = getNode(); // 获取一个未分组的歌单 if (u == -1) break; int col = getCol(u); // 获取可以使用的最小分组编号 colors[u] = col; ans = Math.max(ans, col); for (int v : g[u]) { if (colors[v] == -1) { used[v].add(col); } } } System.out.println(ans + 1); // 输出最小合并歌单数量 sc.close(); }}

时空复杂度

时间复杂度：O(n^2)。

空间复杂度：O(n)。

华为二面，轻松拿下！

题目描述

输入格式

输出格式