union find很适合那种那几个应该在同一队里已经告诉你的题，如果说像group anagram这种哪些要group在一起还要你自己去找的就不太合适
int find(int[] leader, int idx) {
// find finds idx's root leader, it also updates its leader when finding it
if (leader[idx] == idx) {
return idx;
}
leader[idx] = find(leader, leader[idx]);
}
int union(int[]size, int[]leader, int a, int b) {
// union unites two groups
int leadera = find(leader, a);
int leaderb = find(leader, b);
if (leadera == leaderb) {
return 0;
}
if (size[leadera] >= size[leaderb]) {
leader[leaderb] = leadera;
//只要leader对应的size时正确的就好了，非leader的size其实没意义，下同
size[leadera] += size[leaderb];
} else {
leader[leadera] = leaderb;
size[leaderb] += size[leadera];
}
return 1;
}
也可以不union by size，但是始终注意union时是update root的leader
class Union {
int[] leaders;
public Union(int n) {
this.leaders = new int[n];
for (int i = 0; i < n; i++) {
this.leaders[i] = i;
}
}
public int union(int l, int r) {
int leaderl = find(l);
int leaderr = find(r);
if (leaderl == leaderr) {
return 0;
}
leaders[leaderr] = leaderl;
return 1;
}
public int find(int i) {
if (leaders[i] == i) {
return i;
}
leaders[i] = find(leaders[i]);
return leaders[i];
}
}