C++刷leetcode（765. 情侣牵手）【并查集】
题目描述：N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。
这些情侣的初始座位 row 是由最初始坐在第 i 个座位上的人决定的。
示例 1:
输入: row =
输出: 1
解释: 我们只需要交换row和row的位置即可。
示例 2:
输入: row =
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。
说明:
len(row) 是偶数且数值在 范围内。
可以保证row 是序列 0...len(row)-1 的一个全排列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/couples-holding-hands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int find_root(int x, vector<int>& father){
if(father != x) return find_root(father, father);
return x;
}
void uniton(int x, int y, vector<int>& father, vector<int> & rank){
int temp1 = find_root(x, father);
int temp2 = find_root(y, father);
if(temp1 == temp2)return;
else{
if(rank > rank){
father = temp1;
}else if(rank <= rank){
father = temp2;
if(rank == rank){
rank++;
}
}
}
}
int minSwapsCouples(vector<int>& row) {
int len = row.size();
vector<int> father(len/2, 0);
vector<int> rank(len/2, 0);
for(int i = 0; i < len / 2; i++){
father = i;
rank = 1;
}
for(int i = 0; i < len; i+=2){
uniton(row / 2, row/2, father, rank);
}
int circle = 0;
for(int i = 0; i < len / 2; i++){
if(i == father) circle++;
}
return len/2 - circle;
}
};
注意事项：
1.每个情侣就是一个具有两个元素的环，情侣不邻座的时候会出现大于两个元素的偶数个元素的环。 {:10_284:}
页:
[1]