并查集注意两点:
建立边关系用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(); } } }