题解

题面描述

终端部门为了对穿戴设备进行交叉测试，目前有$n$名员工投入测试，人员从$1$到$n$依次编号。为了充分测试和暴露问题，要求任何两个以前戴过同一穿戴设备的人不能再次测同一设备。下面会给出测试投入的人数和测过同一台设备的人员编号，请按照此关系，计算这次至少需要几台穿戴设备供测试。

解题思路

将员工和他们之前使用相同设备的关系建模为图的顶点和边，通过应用DSATUR图着色算法，为每个员工分配不同的颜色，确保任何两个曾共同使用过设备的员工不会分配到相同的颜色。最终，通过确定所需的最少颜色数，即可得到测试所需的最少穿戴设备数量。

1. 建图：根据输入的关系，构建一个无向图，节点代表员工，边代表两个员工曾经使用过同一台设备。
2. DSATUR算法：
   • 初始化：为每个顶点分配一个颜色，初始为未着色（-1）。计算每个顶点的度数和饱和度（与其相邻的不同颜色的数量）。
   • 选择顶点：每次选择未着色且具有最高饱和度的顶点进行着色。如果存在多个顶点具有相同的最高饱和度，则选择度数最大的顶点。
   • 分配颜色：为选定的顶点分配最小的可用颜色，即未被其邻居使用的最小颜色编号。
   • 更新饱和度：为被着色顶点的所有未着色邻居更新其饱和度。
   • 重复：直到所有顶点都被着色。
3. 结果：最终的染色数即为所需的最少穿戴设备数量。

代码

cpp

#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;
    
    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;
}

python

import sys
from collections import defaultdict

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

    def choose_vertex():
        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
        return clr

    max_color = -1
    for _ in range(N):
        v = choose_vertex()
        if v == -1:
            break
        clr = get_color(v)
        colors[v] = clr
        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
    return max_color + 1

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    graph = defaultdict(set)
    for _ in range(M):
        X = int(input[idx]) - 1
        Y = int(input[idx+1]) - 1
        idx += 2
        graph[X].add(Y)
        graph[Y].add(X)
    # 转换为列表
    adj = [graph[i] for i in range(N)]
    chromatic_num = dsatur(N, adj)
    print(chromatic_num)

if __name__ == "__main__":
    main()

java

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

public class Main {
    // DSATUR 算法实现
    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();
        }
        // 记录每个顶点邻居已使用的颜色
        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;
    }

    // 选择下一个要着色的顶点
    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;
    }

    // 获取可用的最小颜色
    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) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        int N = Integer.parseInt(first[0]);
        String[] second = br.readLine().split(" ");
        int M = Integer.parseInt(second[0]);
        // 初始化邻接表
        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++) {
            String[] edge = br.readLine().split(" ");
            int X = Integer.parseInt(edge[0]) - 1; // 转换为 0-based 索引
            int Y = Integer.parseInt(edge[1]) - 1; // 转换为 0-based 索引
            graph.get(X).add(Y);
            graph.get(Y).add(X);
        }
        // 计算色数
        int chromatic_num = dsatur(N, graph);
        System.out.println(chromatic_num);
    }
}

题目内容

终端部门为了对穿戴设备进行交叉测试，目前有$n$名员工投入测试，人员从$1$到$n$依次编号。为了充分测试和暴露问题，要求任何两个以前戴过同一穿戴设备的人不能再次测同一设备。下面会给出测试投入的人数和测过同一台设备的人员编号，请按照此关系，计算这次至少需要几台穿戴设备供测试

输入描述

第一行，一个整数$n(1<n<100)$，表示参加测试的人数，人员从$1$到$n$依次编号。

第二行，一个整数$m$，表示接下来有$m$行数据，$1<=m<=C(n,2)$

以下$m$行每行的格式为:两个整数$a，b，$分别表示员工$a$和$b$，用空格分开$(1<=a,b<=n)$表示员工$a$与员工$b$以前测过同一穿戴设备。

输出描述

输出为一个整数，表示至少需要几台穿戴设备供测试。

样例1

输入

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5

输出

4

说明

$5$个人投入，用连线标记以前测过同一设备的人的关系，不能再测相同设备用颜色标记，可以看出至少需要$4$台穿戴设备供测试

样例2

输入

5
10 
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

输出

5

说明

$5$个人投入，用连线标记以前测过同一设备的人的关系，不能再测相同设备用颜色标记，测过同一设备的人较多，可以看出至少需要$5$台穿戴设备供测试