并查集注意两点:
建立边关系用join;
边关系建立完之后也要对每个节点做一个找父亲的动作,因为边关系的建立仅仅在原父节点之间确定,而原父节点下的子节点无法及时知晓新的父节点是谁。
比如有A节点,B节点,B节点下有b1,b2,b3。建立边关系时仅仅是让A变成B的父亲,这就结束了,但是b1,b2,b3的parent数组还未及时更新,即不知晓B有了新的父亲。对每个节点做一个找父亲的动作find就可以更新了。
class Solution {
public int minSwapsCouples(int[] row) {
Union union=new Union(row.length/2);
for(int i=0;i<row.length;i+=2){
if(row[i]/2!=row[i+1]/2)
union.join(row[i]/2,row[i+1]/2);
}
for(int i=0;i<row.length/2;i++)//这一步也很重要。不可缺少。因为父亲可能有课=了新的父亲,而在建立边关系时没有考虑这一点
union.find(i);
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<row.length/2;i++){
map.put(union.parent[i],map.getOrDefault(union.parent[i],0)+1);
}
int cnt=0;
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
int key=entry.getKey();
int value=entry.getValue();
if(value!=1)
cnt+=value-1;
}
return cnt;
}
class Union{
int[] parent;
Union(int size){
parent=new int[size];
for(int i=0;i<size;i++)
parent[i]=i;
}
int find(int x){
int r=x;
while(r!=parent[r])
r=parent[r];
int j;
while(x!=r){
j=parent[x];
parent[x]=r;
x=j;
}
return r;
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy)
parent[fy]=fx;
}
void print(){
for(int i=0;i<parent.length;i++)
System.out.print(parent[i]+" ");
System.out.println();
}
}
}