947. Most Stones Removed with Same Row or Column

Find connected components, with some specific connected component, the remove count is Num of elements - 1.

First method is to use BFS.

class Solution {        public int removeStones(int[][] stones) {            int N = stones.length;            int[] visited = new int[N];            int ret = 0;            Queue
    
      q = new LinkedList<>();            for (int i = 0; i < N; ++i) {                if (visited[i] == 0) {                    q.add(i);                }                int tmp = 0;                while (!q.isEmpty()) {                    Integer pos = q.poll();                    int x = stones[pos][0], y = stones[pos][1];                    if (visited[pos] == 1) continue;                    tmp += 1;                    visited[pos] = 1;                    for (int j = 0; j < N; ++j) {                        if (visited[j] == 0 && (stones[j][0] == x || stones[j][1] == y)) {                            q.add(j);                        }                    }                }                ret += (tmp != 0 ? (tmp - 1) : 0);            }            return ret;        }    }
    

Also, for finding connected components problem. Union-find algorithm is an efficient algorithm.

And for simplicity, we only use path compression trick.

suppose x is connected components size

result is N - x

class Solution {        public int removeStones(int[][] stones) {            DSU dsu = new DSU(20001);            for (int i = 0; i < stones.length; ++i) {                dsu.union(stones[i][0], 10000 + stones[i][1]);            }            Set
    
      seen = new HashSet<>();            for (int i = 0; i < stones.length; ++i) {                seen.add(dsu.find(stones[i][0]));            }            return stones.length - seen.size();        }                static public class DSU {            int[] parents;            public DSU(int N) {                parents = new int[N];                for (int i = 0; i < N; ++i) parents[i] = i;            }                        public int find(int x) {                if (x != parents[x]) {                    parents[x] = find(parents[x]);                }                return parents[x];            }                        public void union(int x, int y) {                parents[find(x)] = parents[find(y)];            }        }    }