# 读取歌单数量 N 和 歌单重复记录数 M n, 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)] # 获取一个尚未分配分组的歌单（优先选择已用分组数少且连接度高的） defget_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 可使用的最小分组编号 defget_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 开始的，所以最终答案需要加 1 print(ans + 1)
C++
#include #include #include #include usingnamespacestd; // 全局变量定义 int n, m; // 歌单数量 n 和 歌单重复记录数 m vector<vector<int>> g; // 邻接表 g，用于记录哪些歌单有相同歌曲 vector<int> colors; // 记录每个歌单的分组编号，-1 表示未分组 vector<int> deg; // 记录每个歌单的连接度（即它与多少个歌单有相同歌曲） vector<set<int>> used; // 记录每个歌单的邻接歌单已使用的分组编号 // 获取一个尚未分组的歌单编号 intget_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 可以使用的最小分组编号 intget_col(int v){ int val = 0; while (used[v].count(val)) { // 如果该编号已被邻接歌单使用，则尝试下一个编号 val++; } return val; } intmain(){ 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.*; publicclassMain{ // 全局变量定义 staticint n, m; // 歌单数量 n 和 歌单重复记录数 m static ArrayList[] g; // 邻接表 g，记录哪些歌单有相同歌曲 staticint[] colors; // 记录每个歌单的分组编号，-1 表示未分组 staticint[] deg; // 记录每个歌单的连接度 static HashSet[] used; // 记录每个歌单的邻接歌单已使用的分组编号 // 获取一个尚未分组的歌单编号 staticintgetNode(){ 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 可以使用的最小分组编号 staticintgetCol(int v){ int val = 0; while (used[v].contains(val)) { val++; // 如果该编号已被邻接歌单使用，则尝试下一个编号 } return val; } // 比较两个数组的大小 staticintcompareArrays(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; } publicstaticvoidmain(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(); } }
