// 定义并查集结构体
struct UnionFind {
    father: Vec<i32>, // 父节点数组
    size: Vec<i32>,   // 子树大小数组
    help: Vec<i32>,   // 辅助数组，用于优化路径压缩操作
    sets: i32,        // 当前连通分量数
}

impl UnionFind {
    // 初始化并查集
    fn new(n: i32) -> Self {
        let mut father = vec![0; n as usize]; // 初始化父节点数组
        let size = vec![1; n as usize]; // 初始化子树大小数组
        for i in 0..n {
            father[i as usize] = i; // 父节点初始化为自身
        }
        UnionFind {
            father, // 返回新建的并查集结构体
            size,
            help: vec![0; n as usize],
            sets: n, // 初始时连通分量数为n
        }
    }

    // 查找i所在连通分量的代表元素
    fn find(&mut self, mut i: i32) -> i32 {
        let mut hi = 0;
        while i != self.father[i as usize] {
            // 不断向上寻找父节点，直到找到根节点
            self.help[hi] = i; // 将当前节点压入辅助数组中
            hi += 1;
            i = self.father[i as usize]; // 向上跳一步
        }
        for j in (0..hi).rev() {
            // 压缩路径
            self.father[self.help[j] as usize] = i; // 将辅助数组中的节点的父节点设为根节点
        }
        i // 返回根节点
    }

    // 合并i和j所在的连通分量
    fn union(&mut self, i: i32, j: i32) {
        let fi = self.find(i); // 找到i的代表元素
        let fj = self.find(j); // 找到j的代表元素
        if fi != fj {
            // 如果i和j不在同一个连通分量中
            if self.size[fi as usize] >= self.size[fj as usize] {
                // 以树的大小来优化合并操作
                self.father[fj as usize] = fi; // 将fj的父节点设为fi
                self.size[fi as usize] += self.size[fj as usize]; // 更新fi子树的大小
            } else {
                self.father[fi as usize] = fj; // 将fi的父节点设为fj
                self.size[fj as usize] += self.size[fi as usize]; // 更新fj子树的大小
            }
            self.sets -= 1; // 连通分量数减1
        }
    }

    // 获取当前连通分量数
    fn sets(&self) -> i32 {
        self.sets
    }
}

// 计算最少交换座位的次数
fn min_swaps_couples(row: Vec<i32>) -> i32 {
    let n = row.len() as i32; // 座位数量
    let mut uf = UnionFind::new(n / 2); // 初始化并查集
    for i in (0..n).step_by(2) {
        // 遍历相邻的座位
        uf.union(row[i as usize] / 2, row[(i + 1) as usize] / 2); // 合并情侣所在的连通分量
    }
    n / 2 - uf.sets() // 返回需要交换座位的最小次数
}

fn main() {
    let row = vec![0, 2, 1, 3];
    let swaps = min_swaps_couples(row);
    println!("Minimum swaps required: {}", swaps); // Output: Minimum swaps required: 1

    let row = vec![3, 2, 0, 1];
    let swaps = min_swaps_couples(row);
    println!("Minimum swaps required: {}", swaps); // Output: Minimum swaps required: 0
}