Leetcode-947.移除最多的同行或同列的石头

947. 移除最多的同行或同列石头
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：

1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
   石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。

解题思路
将同行或同列，视为在同一个连通集中，则每个连通集都可以删除到只剩一个节点
所以利用并查集求出连通集的个数，就可以知道剩几个节点---相减就是删除几个节点
运行结果
并查集：按点

并查集：按边

java代码

class Solution {
    //find和union共用
    /*//按点并查集
    int[] parent;
    public int removeStones(int[][] stones) {
        int n=stones.length;
        parent=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
        for(int i=0;i<n;i++){//将所有点两两求union
            for(int j=i+1;j<n;j++){
                if(stones[i][0]==stones[j][0] || stones[i][1]==stones[j][1]){
                    union(i,j);
                }
            }
        }
        int cnt=0;
        for(int i=0;i<n;i++){
            if(parent[i]==i) cnt++;
        }
        return n-cnt;
    }*/
    //按边并查集
    int[] parent=new int[20005];
    public int removeStones(int[][] stones) {
        int n=stones.length;
        for(int i=0;i<20005;i++) parent[i]=i;
        for(int[] stone:stones){//对每个点的横纵坐标求union--同行或同列则直接一样
            union(stone[0],stone[1]+10000);
        }
        int cnt=0;
        Set<Integer> set = new HashSet<>();//set只保存不重复的数据
        for(int[] stone:stones){
            set.add(find(stone[0]));
        }
        return n-set.size();

    }
    public void union(int x,int y){
        parent[find(x)]=find(y);
    }

    public int find(int x){
        if(parent[x]==x){
            return parent[x];
        }
        else{
            return find(parent[x]);
        }
    }

}