#[derive(Clone, Debug, PartialEq)]
pub struct UnionFindElement {
    idx: usize,
    parent: usize,
}

/// A structure for representing components with nodes.
#[derive(Clone, Debug, PartialEq)]
pub struct UnionFind {
    elements: Vec<UnionFindElement>
}

impl UnionFind {
    pub fn make_set(len: usize) -> UnionFind {
        UnionFind {
            elements: (0..len).map(|idx|
                                   UnionFindElement {
                                       idx,
                                       parent: idx
                                   }).collect()
        }
    }

    pub fn len(&self) -> usize {
        self.elements.len()
    }

    /// Find component of a node.
    pub fn find(&self, x: usize) -> usize {
        let mut current = &self.elements[x];
        while current.parent != current.idx {
            current = &self.elements[current.parent];
        }

        current.idx
    }

    /// Connect two components.
    pub fn union(&mut self, x: usize, y: usize) {
        let x = self.find(x);
        let y = self.find(y);

        self.elements[y].parent = x;
    }
}