2022-12-18：给定一个长度为 n 的二维数组 graph，代表一张图， graph[i] = {a,b,c,d} 表示 i 讨厌 (a,b,c,d)，讨厌关系为双向的， 一共有 n 个人，编号 0~n-1， 讨

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