2022-11-04:给定一个正数n,表示有多少个节点给定一个二维数组edges,表示所有无向边edges[i] = {a, b
2023-02-26 09:49:24 时间
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代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_2_week/Code02_TreeDye.java)
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023