# 0947. Most Stones Removed with Same Row or Column
###### tags: `Leetcode` `Medium` `Union Find` `Union Find by Index`
Link: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
## 思路
### 思路一 Group by Points $O(N^2)$
把相同row或者相同col的全都group在一起
每个group只留一个stone
### 思路二 Group by Indices $O(N)$
思路[参考](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/solutions/197668/count-the-number-of-islands-o-n/)
每次新加一个点 我们把```row```跟```col``` group在一起
如果我们按照思路一 把row相同或col相同的merge在一起 那么每个group只留一个point 所以```stones.size()-islands of points```就是答案
又因为**the number of islands of points is the same as the number of islands of indices**
所以```stones.size()-islands of indices```也是答案
## Code

class Solution {
    int[] fa;
    int group;
    public int removeStones(int[][] stones) {
        int n = stones.length;
        fa = new int[n];
        group = stones.length;
        for(int i=0; i<n; i++) fa[i] = i;
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(stones[i][0]==stones[j][0] || stones[i][1]==stones[j][1]) combine(i, j);
            }
        }
        return stones.length-group;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a]=find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        group--;
        fa[b]=a;
    }
}