2022-11-04：给定一个正数 n，表示有多少个节点 给定一个二维数组 edges，表示所有无向边 edges[i] = {a, b} 表示 a 到 b 有一条无向边 edges 一定表示的是一个无环无向图，也

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 3const RULE1: [i32; 3] = [1, 2, 3];
// // 1 3 2 1 3 2 1 3 2const 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;}