947. Most Stones Removed with Same Row or Column

Version #1 Union Find

首先完全没思路，看了答案才知道是个number of island的题
然后对于UF中的id，一开始脑子抽了用hash = y * cols + x导致MLE
后来发现原来就直接用stones的index就完全可以表示id了。。。 mdzz

class Solution {
    int[] id;
    int[] size;
    int count;
    public int removeStones(int[][] stones) {
        count = 0;
        int len = stones.length;
        id = new int[len];
        size = new int[len];
        for (int i = 0; i < len; i++) {
            id[i] = i;
            size[i] = 1;
            count++;
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    connect(i, j);
                }
            }
        }
        return stones.length - count;
    }
   
    private int root(int i) {
        while (id[i] != i) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
   
    private void connect(int p, int q) {
        int rootP = root(p);
        int rootQ = root(q);
        if (rootP == rootQ) {
            return;
        }
        count--;
        if (size[rootP] < size[rootQ]) {
            id[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            id[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
    }
}