题目内容

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

给定一个包含 $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$ 一组。

题解

题面描述

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

问题转化

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

• 顶点（Vertices）：每个歌单对应一个顶点。
• 边（Edges）：如果两个歌单有相同的歌曲，则在对应的两个顶点之间画一条边。
• 图着色（Graph Coloring）：为每个顶点分配一种颜色，要求相邻的顶点颜色不同。

最终，最小合并歌单数即为图的染色数（Chromatic Number），即能够满足上述条件的最少颜色数。

解题步骤

1. 构建图

根据输入的数据，首先构建一个无向图：

• 初始化 N 个顶点，编号从 0 到 N-1。
• 对于每一条重复记录 (X, Y)，在顶点 X-1 和 Y-1 之间添加一条边。

2. 图着色算法

为了求解图的染色数，可以采用 DSATUR（Degree of Saturation）算法，它是一种贪心算法，能够有效地为图着色，特别适用于中小规模的图（本题中 N <= 100）。

DSATUR 算法简介

DSATUR 算法的核心思想是：

1. 饱和度（Saturation Degree）：一个顶点的饱和度是指与之相邻且已经被着色的顶点所使用的不同颜色的数量。
2. 选择策略：
   • 首先选择未被着色且饱和度最高的顶点。
   • 如果有多个顶点的饱和度相同，则选择度数（与之相连的顶点数量）最大的顶点。
3. 颜色分配：为选中的顶点分配一个最小的可用颜色（即尚未被其邻居使用的最小颜色编号）。

算法步骤

1. 初始化：

   • 所有顶点的颜色初始化为 -1（表示未着色）。
   • 计算每个顶点的度数。
   • 初始化每个顶点的饱和度为 0。
   • 为每个顶点维护一个集合，记录其邻居已使用的颜色。

2. 着色过程：

   • 重复以下步骤，直到所有顶点都被着色：
     • 选择一个未着色且具有最高饱和度的顶点。如果多个顶点具有相同的饱和度，则选择度数最大的顶点。
     • 为该顶点分配一个最小的可用颜色。
     • 更新其邻居的饱和度和已使用颜色集合。

3. 结果：

   • 图的染色数即为所使用的最大颜色编号加一（因为颜色从 0 开始编号）。

python

def dsatur(N, adj):
    # 初始化颜色分配，-1 表示未着色
    colors = [-1] * N
    # 初始化每个顶点的饱和度
    sat = [0] * N
    # 计算每个顶点的度数
    degree = [len(neighbors) for neighbors in adj]
    # 记录每个顶点邻居已使用的颜色
    used = [set() for _ in range(N)]

    def choose():
        max_sat = -1
        max_deg = -1
        vertex = -1
        for v in range(N):
            if colors[v] == -1:
                if sat[v] > max_sat or (sat[v] == max_sat and degree[v] > max_deg):
                    max_sat = sat[v]
                    max_deg = degree[v]
                    vertex = v
        return vertex

    def get_color(v):
        clr = 0
        while clr in used[v]:
            clr += 1
        colors[v] = clr
        return clr

    max_color = -1
    for _ in range(N):
        v = choose()
        if v == -1:
            break
        clr = get_color(v)
        if clr > max_color:
            max_color = clr
        # 更新相邻顶点的饱和度
        for neighbor in adj[v]:
            if colors[neighbor] == -1:
                if clr not in used[neighbor]:
                    used[neighbor].add(clr)
                    sat[neighbor] += 1

    # 色数为最高颜色编号加一（因为颜色从0开始）
    return max_color + 1

def main():
    import sys

    # 读取第一行：N 和 M
    N, M = map(int, input().split())

    # 初始化邻接表
    graph = [set() for _ in range(N)]

    # 读取 M 条边
    for _ in range(M):
        X, Y = map(int, input().split())
        # 转换为 0-based 索引
        X -= 1
        Y -= 1
        # 添加边
        graph[X].add(Y)
        graph[Y].add(X)

    # 计算色数
    chromatic_num = dsatur(N, graph)
    print(chromatic_num)

if __name__ == "__main__":
    main()

c++

#include <bits/stdc++.h>
using namespace std;

// DSATUR 算法实现
int dsatur(int N, vector<unordered_set<int>> &adj) {
    // 初始化颜色分配，-1 表示未着色
    vector<int> colors(N, -1);
    // 初始化每个顶点的饱和度
    vector<int> sat(N, 0);
    // 计算每个顶点的度数
    vector<int> degree(N, 0);
    for(int i = 0; i < N; i++) {
        degree[i] = adj[i].size();
    }
    // 记录每个顶点邻居已使用的颜色
    vector<unordered_set<int>> used(N, unordered_set<int>());

    // 选择下一个要着色的顶点
    auto chooseVertex = [&](int N, vector<int> &colors, vector<int> &sat, vector<int> &degree) -> int {
        int maxSat = -1;
        int maxDeg = -1;
        int vertex = -1;
        for(int v = 0; v < N; v++) {
            if(colors[v] == -1) {
                if(sat[v] > maxSat || (sat[v] == maxSat && degree[v] > maxDeg)) {
                    maxSat = sat[v];
                    maxDeg = degree[v];
                    vertex = v;
                }
            }
        }
        return vertex;
    };

    // 获取可用的最小颜色
    auto getColor = [&](int v, vector<unordered_set<int>> &used) -> int {
        int clr = 0;
        while(used[v].count(clr)) {
            clr++;
        }
        return clr;
    };

    int maxColor = -1;
    for(int i = 0; i < N; i++) {
        // 选择下一个要着色的顶点
        int v = chooseVertex(N, colors, sat, degree);
        if(v == -1) {
            break;
        }
        // 分配颜色
        int clr = getColor(v, used);
        colors[v] = clr;
        if(clr > maxColor) {
            maxColor = clr;
        }
        // 更新相邻顶点的饱和度
        for(auto &neighbor : adj[v]) {
            if(colors[neighbor] == -1) {
                if(!used[neighbor].count(clr)) {
                    used[neighbor].insert(clr);
                    sat[neighbor]++;
                }
            }
        }
    }

    // 色数为最高颜色编号加一（因为颜色从0开始）
    return maxColor + 1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, M;
    // 读取第一行：N 和 M
    cin >> N >> M;

    // 初始化邻接表
    vector<unordered_set<int>> graph(N, unordered_set<int>());

    // 读取 M 条边
    for(int i = 0; i < M; i++) {
        int X, Y;
        cin >> X >> Y;
        X -= 1; // 转换为 0-based 索引
        Y -= 1; // 转换为 0-based 索引
        // 添加边
        graph[X].insert(Y);
        graph[Y].insert(X);
    }

    // 计算色数
    int chromatic_num = dsatur(N, graph);
    cout << chromatic_num;
}

java

import java.util.*;
import java.io.*;

public class Main {

    /**
     * DSATUR 算法实现
     * 
     * @param N   图的顶点数
     * @param adj 图的邻接表表示
     * @return 图的色数
     */
    public static int dsatur(int N, List<Set<Integer>> adj) {
        // 初始化颜色分配，-1 表示未着色
        int[] colors = new int[N];
        Arrays.fill(colors, -1);
        
        // 初始化每个顶点的饱和度
        int[] sat = new int[N];
        
        // 计算每个顶点的度数
        int[] degree = new int[N];
        for (int i = 0; i < N; i++) {
            degree[i] = adj.get(i).size();
        }
        
        // 记录每个顶点邻居已使用的颜色
        @SuppressWarnings("unchecked")
        Set<Integer>[] used = new HashSet[N];
        for (int i = 0; i < N; i++) {
            used[i] = new HashSet<>();
        }

        int maxColor = -1; // 记录使用的最大颜色编号

        // 依次为每个顶点着色
        for (int i = 0; i < N; i++) {
            // 选择下一个要着色的顶点
            int v = chooseVertex(N, colors, sat, degree);
            if (v == -1) {
                break; // 所有顶点都已着色
            }

            // 获取可用的最小颜色
            int clr = getColor(v, used);
            colors[v] = clr; // 分配颜色

            if (clr > maxColor) {
                maxColor = clr; // 更新最大颜色编号
            }

            // 更新相邻顶点的饱和度
            for (int neighbor : adj.get(v)) {
                if (colors[neighbor] == -1) { // 仅更新未着色的邻居
                    if (!used[neighbor].contains(clr)) {
                        used[neighbor].add(clr);
                        sat[neighbor]++;
                    }
                }
            }
        }

        // 色数为最高颜色编号加一（因为颜色从0开始）
        return maxColor + 1;
    }

    /**
     * 选择下一个要着色的顶点
     * 
     * @param N      图的顶点数
     * @param colors 当前颜色分配
     * @param sat    当前每个顶点的饱和度
     * @param degree 每个顶点的度数
     * @return 选择的顶点编号
     */
    public static int chooseVertex(int N, int[] colors, int[] sat, int[] degree) {
        int maxSat = -1;
        int maxDeg = -1;
        int vertex = -1;
        for (int v = 0; v < N; v++) {
            if (colors[v] == -1) { // 仅考虑未着色的顶点
                if (sat[v] > maxSat || (sat[v] == maxSat && degree[v] > maxDeg)) {
                    maxSat = sat[v];
                    maxDeg = degree[v];
                    vertex = v;
                }
            }
        }
        return vertex;
    }

    /**
     * 获取顶点 v 可用的最小颜色
     * 
     * @param v    顶点编号
     * @param used 顶点已使用的颜色集合
     * @return 最小可用颜色编号
     */
    public static int getColor(int v, Set<Integer>[] used) {
        int clr = 0;
        while (used[v].contains(clr)) {
            clr++;
        }
        return clr;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取第一行：N 和 M
        int N = scanner.nextInt(); // 顶点数
        int M = scanner.nextInt(); // 边数

        // 初始化邻接表
        List<Set<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            graph.add(new HashSet<>());
        }

        // 读取 M 条边
        for (int i = 0; i < M; i++) {
            int X = scanner.nextInt(); // 顶点 X
            int Y = scanner.nextInt(); // 顶点 Y
            // 转换为 0-based 索引
            X -= 1;
            Y -= 1;
            // 添加边
            graph.get(X).add(Y);
            graph.get(Y).add(X);
        }

        // 计算色数
        int chromatic_num = dsatur(N, graph);
        System.out.println(chromatic_num);
        
        scanner.close(); // 关闭扫描器
    }
}