947. Most Stones Removed with Same Row or Column

Link

Solution

將node分群的概念，每群只會留一個，同群之間會有row or colum相同的關係

最後刪除的元素就是所有stone數-group數

T : O(N^2)

 public int removeStones(int[][] stones) {
        int N = stones.length;
        int[] group = new int[N];
        int groupId= 0;
        for(int i = 0; i < stones.length; i++){
            if(color[i] == 0){
                groupId++;
                dfs(stones, i, group , groupId);
            }
        }
        return N - groupId;
    }
    
    public void dfs(int[][] stones, int i, int[] group , int groupId){
        if(group[i] == groupId) return;
        
        group[i] = groupId;
        
        for(int j = 0; j < stones.length; j++){
            if(i == j) continue;
            if(group[j] != 0) continue;
            
            if(stones[j][0] == stones[i][0] || stones[j][1] == stones[i][1]){
                dfs(stones, j, group , groupId);   
            }
        }
    }