2022-12-18:给定一个长度为n的二维数组graph,代表一张图, graph[i] =

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代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!