Union find

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];
        }
    }

在已经union好了之后，可以通过遍历index找他们对应的leader的方式遍历union里所有group的leader/root