2022-12-18:给定一个长度为n的二维数组graph,代表一张图,graph[i] = {a,b,c,d} 表示i讨厌(a
2023-02-26 09:49:34 时间
2022-12-18:给定一个长度为n的二维数组graph,代表一张图,
graph[i] = {a,b,c,d} 表示i讨厌(a,b,c,d),讨厌关系为双向的,
一共有n个人,编号0~n-1,
讨厌的人不能一起开会。
返回所有人能不能分成两组开会。
来自微软面试。
答案2022-12-18:
力扣785。并查集。
代码用rust编写。代码如下:
use rand::Rng;
use std::iter::repeat;
fn main() {
let mut graph: Vec<Vec<i32>> = vec![vec![1, 2, 3], vec![0, 2], vec![0, 1, 3], vec![0, 2]];
let ans = is_bipartite(&mut graph);
println!("ans = {}", ans);
}
fn is_bipartite(graph: &mut Vec<Vec<i32>>) -> bool {
let n = graph.len() as i32;
let mut uf = UnionFind::new(n);
for neighbours in graph.iter() {
for i in 1..neighbours.len() as i32 {
uf.union(neighbours[(i - 1) as usize], neighbours[i as usize]);
}
}
for i in 0..n {
for j in graph[i as usize].iter() {
if uf.same(i, *j) {
return false;
}
}
}
return true;
}
struct UnionFind {
f: Vec<i32>,
s: Vec<i32>,
h: Vec<i32>,
}
impl UnionFind {
pub fn new(n: i32) -> Self {
let mut f: Vec<i32> = repeat(0).take(n as usize).collect();
let mut s: Vec<i32> = repeat(0).take(n as usize).collect();
let mut h: Vec<i32> = repeat(0).take(n as usize).collect();
for i in 0..n {
f[i as usize] = i;
s[i as usize] = 1;
}
Self { f, s, h }
}
fn find(&mut self, mut i: i32) -> i32 {
let mut hi = 0;
while i != self.f[i as usize] {
self.h[hi as usize] = i;
hi += 1;
i = self.f[i as usize];
}
while hi > 0 {
hi -= 1;
self.f[self.h[hi as usize] as usize] = i;
}
return i;
}
pub fn same(&mut self, i: i32, j: i32) -> bool {
return self.find(i) == self.find(j);
}
pub fn union(&mut self, i: i32, j: i32) {
let mut fi = self.find(i);
let mut fj = self.find(j);
if fi != fj {
if self.s[fi as usize] >= self.s[fj as usize] {
self.f[fj as usize] = fi;
self.s[fi as usize] = self.s[fi as usize] + self.s[fj as usize];
} else {
self.f[fi as usize] = fj;
self.s[fj as usize] = self.s[fi as usize] + self.s[fj as usize];
}
}
}
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_09_1_week/Code05_IsGraphBipartite.java)
相关文章
- 用 Java 写个塔防游戏「GitHub 热点速览 v.21.37」
- 这款打怪升级的小游戏,7 年前出生于 GitHub 社区,如今在谷歌商店有 8 万人打了满分
- 开源的 Web 框架哪个快?我在 GitHub 找到了答案
- 人生重开模拟器「GitHub 热点速览 v.21.36」
- 自建纯净谷歌搜索「GitHub 热点速览 v.21.35」
- 早产的《HelloGitHub》第 65 期
- 5 秒克隆声音「GitHub 热点速览 v.21.34」
- 那些 Unix 命令替代品们「GitHub 热点速览 v.21.32」
- 承载童年的游戏机,已停产!但我在 GitHub 找到了它们
- 自制车速记录仪「GitHub 热点速览 v.21.31」
- 开源百宝箱《HelloGitHub》第 64 期
- 在线体验 Windows 11「GitHub 热点速览 v.21.30」
- AI 预测蛋白质结构「GitHub 热点速览 v.21.29」
- 获取 Windows 密码「GitHub 热点速览 v.21.28」
- 互联网巨头们的 SRE 运维实践「GitHub 热点速览 v.21.27」
- 我成了 GitHub Star
- 你的电脑适合升级 Win11 吗?「GitHub 热点速览 v.21.26」
- 有趣的开源项目集结完毕,HelloGitHub 月刊第 63 期发布啦!
- 魔镜魔镜,今天有雨吗?——GitHub 热点速览 v.21.25
- 徒手用 Go 写个 Redis 服务器(Godis)