免费特黄视频_国产精品久久久av_久久香蕉网_国产精彩视频_中文二区_国产成人一区

二維碼
企資網

掃一掃關注

當前位置: 首頁 » 企資快報 » 精準 » 正文

2022_11_04_給定一個正數n_表示有多

放大字體  縮小字體 發布日期:2022-11-29 14:49:06    作者:葉承宇    瀏覽次數:63
導讀

2022-11-04:給定一個正數n,表示有多少個節點給定一個二維數組edges,表示所有無向邊edges[i] = {a, b} 表示a到b有一條無向邊edges一定表示得是一個無環無向圖,也就是樹結構每個節點可以染1、2、3三種顏色。要求 :

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

執行結果如下:

***

[左神java代碼](github/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_2_week/Code02_TreeDye.java)

 
(文/葉承宇)
免責聲明
本文僅代表作發布者:葉承宇個人觀點,本站未對其內容進行核實,請讀者僅做參考,如若文中涉及有違公德、觸犯法律的內容,一經發現,立即刪除,需自行承擔相應責任。涉及到版權或其他問題,請及時聯系我們刪除處理郵件:weilaitui@qq.com。
 

Copyright ? 2016 - 2025 - 企資網 48903.COM All Rights Reserved 粵公網安備 44030702000589號

粵ICP備16078936號

微信

關注
微信

微信二維碼

WAP二維碼

客服

聯系
客服

聯系客服:

在線QQ: 303377504

客服電話: 020-82301567

E_mail郵箱: weilaitui@qq.com

微信公眾號: weishitui

客服001 客服002 客服003

工作時間:

周一至周五: 09:00 - 18:00

反饋

用戶
反饋

主站蜘蛛池模板: 国产精品黄色 | 久久久久久网站 | 国产欧美一区二区三区久久手机版 | 午夜小影院 | 欧美a∨ | 欧美www在线| 国产精品久久久久久久久久久免费看 | 99亚洲精品| 婷婷激情在线 | 国产一区二 | 国产精品精品视频一区二区三区 | 99久久婷婷国产综合精品首页 | 国产一区二区三区精品久久久 | 欧美一级观看 | 久草在线在线精品观看 | 国产成人精品一区二区三区四区 | 毛片一级片 | 欧美日韩一区在线 | 久久男人| 亚洲不卡一 | 综合激情久久 | 国产精品视频在线播放 | 日韩在线小视频 | 精品国产一区二区三区久久久久久 | 中文字幕亚洲欧美日韩在线不卡 | 亚洲欧美成人影院 | 免费国产一区二区 | 国产精品a免费一区久久电影 | 国产一级毛片精品完整视频版 | 综合精品久久久 | 黄色a视频 | 亚洲国产aⅴ精品一区二区 免费观看av | 久久青| 在线播放国产一区二区三区 | 精品国产一区二区三区久久 | 黄网免费 | 久久99深爱久久99精品 | 欧美三级视频 | 国产美女黄色片 | 夜夜爽99久久国产综合精品女不卡 | 亚洲激精日韩激精欧美精品 |