947. Most Stones Removed with Same Row or Column

 1import java.util.HashSet;
 2import java.util.Set;
 3
 4/**
 5 * @author lxn
 6 * @description 947. Most Stones Removed with Same Row or Column
 7 * @create 2020-02-09 20:58
 8 */
 9public class Algorithm947 {
10    public static void main(String[] args) {
11        int[][] stones = {{0, 0}, {0, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 2}};
12        int res = new Solution947().removeStones(stones);
13    }
14}
15
16class Solution947 {
17    public int removeStones(int[][] stones) {
18        int len = stones.length;
19        DSU dsu = new DSU(20000); // 初始化。DSU有一个属性int pre[]，一个构造函数 和 两个方法
20        for(int i = 0; i < len; i++){ // 遍历
21            dsu.union(stones[i][0], stones[i][1] + 10000); // 每次拿出stones中的一个点，x是第一个数，y是第二个数加20000。加上这个是为了降维，将2D转为1D,将纵坐标+1000，就能简单区分横纵坐标。
22        }
23        Set<Integer> set = new HashSet();
24        // 查看连通子图的数量
25        for(int[] stone : stones){
26            set.add(dsu.find(stone[0]));
27        }
28        return len - set.size();
29    }
30}
31
32//构建并查集类
33class DSU{
34    int pre[];
35    public DSU(int n){
36        pre = new int[n];
37        for(int i = 0; i < n; i++){
38            pre[i] = i; // 每个元素初始化根节点是自己
39        }
40    }
41    public int find(int x){// 找到某个节点的父节点
42        while(pre[x] != x){
43            x = pre[x];
44        }
45        return x;
46    }
47    public void union(int x, int y){ // 宣告两个节点同属于一个group
48        int fx = find(x);
49        int fy = find(y);
50        if(fx != fy){
51            pre[fx] = fy;
52        }
53    }
54}