pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
    use std::collections::HashSet;
    use std::collections::VecDeque;

    let mut queue = VecDeque::new();
    let mut visited = HashSet::new();

    queue.push_back(0);
    visited.insert(0);
    while let Some(n) = queue.pop_front() {
        let room = rooms.get(n).unwrap();
        for &r in room.iter(){
            if !visited.insert(r) {
                continue;
            }
            queue.push_back(r as usize)
        }
    }
    visited.len() == rooms.len()
}

pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
    use std::collections::VecDeque;
    let mut uf = UnionFind::new(rooms.len());

    let mut queue = VecDeque::new();

    queue.push_back(0);
    while let Some(curr) = queue.pop_front() {
        let room = rooms.get(curr).unwrap();
        for &r in room.iter() {
            if uf.is_connected(curr, r as usize) {
                continue;
            }
            uf.connect(curr, r as usize);
            queue.push_back(r as usize);
        }
    }
    uf.count() == 1
}

struct UnionFind {
    count: usize,                           // 连通分量的个数, 总共分成了几组
    parent: std::cell::RefCell<Vec<usize>>, // 记录每个节点的父节点，父节点为自身的是根节点
    size: Vec<usize>,                       // 记录每个连通分量的大小
}

impl UnionFind {
    pub fn new(size: usize) -> Self {
        Self {
            count: size,
            parent: std::cell::RefCell::new((0..size).collect()),
            size: vec![1; size],
        }
    }
    pub fn count(&self) -> usize {
        self.count
    }
    pub fn find(&self, p: usize) -> usize {
        let mut root = p;
        while root != self.parent.borrow()[root] {
            root = self.parent.borrow()[root];
        }
        let mut p = p;
        while p != root {
            let next = self.parent.borrow()[p];
            self.parent.borrow_mut()[p] = root;
            p = next;
        }
        root
    }

    pub fn is_connected(&self, p: usize, q: usize) -> bool {
        self.find(p) == self.find(q)
    }
    pub fn connect(&mut self, p: usize, q: usize) {
        let (p_root, q_root) = (self.find(p), self.find(q));
        if p_root == q_root {
            return;
        }
        if self.size[p_root] < self.size[q_root] {
            self.parent.borrow_mut()[p_root] = q_root;
            self.size[q_root] += self.size[p_root];
        } else {
            self.parent.borrow_mut()[q_root] = p_root;
            self.size[p_root] += self.size[q_root];
        }
        self.count -= 1;
    }
}