class Solution { int maxn = 20005; //根据坐标范围而定 int[] father = new int[maxn]; // 并查集初始化 public void init(){ Arrays.fill(father , -1); } // 并查集里寻根的过程 public int find(int u){ return father[u] == -1 ? u : find(father[u]); } // 将 v -> u 这条边加入并查集 public void union(int u , int v){ int rootu = find(u); int rootv = find(v); if(rootu != rootv){ father[rootv] = rootu; } } // 判断 u 和 v 是否找到同一个根 public boolean same(int u , int v){ return find(u) == find(v); } public int removeStones(int[][] stones) { init(); for(int[] stone : stones){ union(stone[0] , stone[1] + 10000); } Map<Integer , Boolean> umap = new HashMap<>(); for(int[] stone : stones){ umap.put(find(stone[0]) , true); umap.put(find(stone[1] + 10000) , true); } return stones.length - umap.size(); } }
时间: 2023-04-01 11:02:50 浏览: 186
浅析C/C++变量在内存中的分布
这是一段 Java 代码,用于移除一组石头中的冗余石头。它使用并查集来判断两个石头是否在同一个连通块中。具体来说,它将每个石头的行和列看作一个节点,并将它们连接起来,最后统计连通块的数量。移除的石头数量等于总石头数量减去连通块数量。
我可以回答这个问题。
阅读全文