2022-11-04：给定一个正数n，表示有多少个节点 给定一个二维数组edges，表示所有无向边 edges[i]

2022-11-04：给定一个正数n，表示有多少个节点
给定一个二维数组edges，表示所有无向边
edges[i] = {a, b} 表示a到b有一条无向边
edges一定表示的是一个无环无向图，也就是树结构
每个节点可以染1、2、3三种颜色。
要求 : 非叶节点的相邻点一定要至少有两种和自己不同颜色的点。
返回一种达标的染色方案，也就是一个数组，表示每个节点的染色状况。
1 <= 节点数量 <= 10的5次方。
来自米哈游。

答案2022-11-04：

生成图，选一个头节点，深度优先染色。

代码用rust编写。代码如下：

use std::{iter::repeat, vec};

use rand::Rng;
fn main() {
    let nn: i32 = 100;
    let test_time: i32 = 1000;
    println!("测试开始");
    for i in 0..test_time {
        let n = rand::thread_rng().gen_range(0, nn) + 1;
        let mut edges = random_edges(n);
        let mut ans = dye(n, &mut edges);
        if !right_answer(n, &mut edges, &mut ans) {
            println!("出错了!{}", i);
            break;
        }
    }
    println!("测试结束");
}

// 1 2 3 1 2 3 1 2 3
const RULE1: [i32; 3] = [1, 2, 3];

// // 1 3 2 1 3 2 1 3 2
const RULE2: [i32; 3] = [1, 3, 2];

fn dye(n: i32, edges: &mut Vec<Vec<i32>>) -> Vec<i32> {
    let mut graph: Vec<Vec<i32>> = vec![];
    // 0 : { 2, 1 }
    // 1 : { 0 }
    // 2 : { 0 }
    for _i in 0..n {
        graph.push(vec![]);
    }
    for edge in edges.iter() {
        // 0 -> 2
        // 1 -> 0
        graph[edge[0] as usize].push(edge[1]);
        graph[edge[1] as usize].push(edge[0]);
    }
    // 选一个头节点！
    let mut head = -1;
    for i in 0..n {
        if graph[i as usize].len() >= 2 {
            head = i;
            break;
        }
    }
    // graph
    // head
    let mut colors: Vec<i32> = repeat(0).take(n as usize).collect();
    if head == -1 {
        // 两个点，互相连一下
        // 把colors，所有位置，都设置成1
        colors = repeat(1).take(n as usize).collect();
    } else {
        // dfs 染色了！
        colors[head as usize] = 1;
        let h = graph[head as usize][0];
        dfs(&mut graph, h, 1, &RULE1, &mut colors);
        for i in 1..graph[head as usize].len() as i32 {
            let h = graph[head as usize][i as usize];
            dfs(&mut graph, h, 1, &RULE2, &mut colors);
        }
    }
    return colors;
}

// 整个图结构，都在graph
// 当前来到的节点，是head号节点
// head号节点，在level层
// 染色的规则，rule {1,2,3...} {1,3,2...}
// 做的事情：以head为头的整颗树，每个节点，都染上颜色
// 填入到colors数组里去
fn dfs(graph: &mut Vec<Vec<i32>>, head: i32, level: i32, rule: &[i32; 3], colors: &mut Vec<i32>) {
    colors[head as usize] = rule[(level % 3) as usize];
    for next in graph[head as usize].clone().iter() {
        if colors[*next as usize] == 0 {
            dfs(graph, *next, level + 1, rule, colors);
        }
    }
}

// 为了测试
// 生成无环无向图
fn random_edges(n: i32) -> Vec<Vec<i32>> {
    let mut order: Vec<i32> = repeat(0).take(n as usize).collect();
    for i in 0..n {
        order[i as usize] = i;
    }
    let mut i = n - 1;

    while i >= 0 {
        order.swap(i as usize, rand::thread_rng().gen_range(0, i + 1) as usize);
        i -= 1;
    }
    let mut edges: Vec<Vec<i32>> = repeat(repeat(0).take(2).collect())
        .take((n - 1) as usize)
        .collect();
    for i in 1..n {
        edges[(i - 1) as usize][0] = order[i as usize];
        edges[(i - 1) as usize][1] = order[rand::thread_rng().gen_range(0, i) as usize];
    }
    return edges;
}

// 为了测试
fn right_answer(n: i32, edges: &mut Vec<Vec<i32>>, colors: &mut Vec<i32>) -> bool {
    let mut graph: Vec<Vec<i32>> = vec![];
    for _i in 0..n {
        graph.push(vec![]);
    }
    for edge in edges.iter() {
        graph[edge[0] as usize].push(edge[1]);
        graph[edge[1] as usize].push(edge[0]);
    }
    let mut has_colors: Vec<bool> = repeat(false).take(4).collect();
    let mut i = 0;
    let mut color_cnt = 1;
    while i < n {
        if colors[i as usize] == 0 {
            return false;
        }
        if graph[i as usize].len() <= 1 {
            // i号点是叶节点
            i += 1;
            color_cnt = 1;
            continue;
        }
        has_colors[colors[i as usize] as usize] = true;
        for near in graph[i as usize].iter() {
            if !has_colors[colors[*near as usize] as usize] {
                has_colors[colors[*near as usize] as usize] = true;
                color_cnt += 1;
            }
        }
        if color_cnt != 3 {
            return false;
        }
        has_colors = repeat(false).take(4).collect();
        i += 1;
        color_cnt = 1;
    }
    return true;
}

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接