# 947. Most Stones Removed with Same Row or Column

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Example 3:

Input: stones = [[0,0]]
Output: 0

Note:

1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

## Solution

1. number of island: dfs, calculate number of components, the result is the difference between number of stones and components
2. union find find采用路径压缩

O(N) O(N)

## Code

``````// dfs

class Solution {
public int removeStones(int[][] stones) {
Set<int[]> set = new HashSet<>();
int numOfIsland = 0;
for(int[] stone : stones){
if(!set.contains(stone)){
dfs(stone, stones, set);
numOfIsland++;
}
}
return stones.length - numOfIsland;
}
public void dfs(int[] s1, int[][] stones, Set<int[]> visited){
if(visited.contains(s1)) return;
for(int[] s2 : stones){
if(s1[0] == s2[0] || s1[1] == s2[1])
dfs(s2, stones, visited);
}

}
}
``````
``````// union find
class Solution {
private int count = 0;
public int removeStones(int[][] stones) {
count = stones.length;
int[] parent = new int[stones.length];
for(int i = 0; i < parent.length; i++) parent[i] = i;

for(int i = 0; i < stones.length; i++){
for(int j = i + 1; j < stones.length; j++){
if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])
union(parent, i, j, stones);
}
}
return stones.length - count;
}
public void union(int[] parent, int i, int j, int[][] stones){
int parent1 = find(parent, i);
int parent2 = find(parent, j);

if(parent1 == parent2) return;

parent[parent2] = parent1;
count--;
}
public int find(int[] parent, int i){
if(parent[i] != i){
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
}
``````