# 947.Most-Stones-Removed-with-Same-Row-or-Column

## 947. Most Stones Removed with Same Row or Column

## 题目地址

<https://leetcode.com/problems/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
```

## 代码

### Approach #2 Union-Find

Time `O(N log N)` Space `O(N)`

```java
class Solution {
  public int removeStones(int[][] stones) {
    int N = stones.length;
    DSU dsu = new DSU(2000);

    for (int[] stone: stones) {
      dsu.union(stone[0], stone[1] + 10000);
    }

    Set<Integer> seen = new HashSet();
    for (int[] stone: stones) {
      seen.add(dsu.find(stone[0]));
    }

    return N - seen.size();
  }
}

class DSU {
  int[] parent;
  public DSU(int N) {
    parent = new int[N];
    for (int i = 0; i < N; i++) {
      parent[i] = i;
    }
  }

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

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

### Appraoch #3 DFS number of islands

```java
class Solution {
  // Ans = # of stones - # of islands
  public int removeStones(int[][] stones) {
    Set<int[]> visited = new HashSet();
    int numOfIslands = 0;
    for (int[] s1: stones) {
      if (!visited.contains(s1)) {
        dfs(s1, visited, stones);
        numOfIslands++;
      }
    }
    return stones.length - numOfIslands;
  }

  private void dfs(int[] s1, Set<int[]> visited, int[][] stones) {
    visited.add(s1);
    for (int[] s2: stones) {
      if (!visited.contains(s2)) {
        // stone with same row or column. group them into island
        if (s1[0] == s2[0] || s1[1] == s2[1]) {
          dfs(s2, visited, stones);
        }
      }
    }
  }
}
```

### Approach #4 BFS

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

```java
class Solution {
  public int removeStones(int[][] stones) {
    int N = stones.length;
    int[] visited = new int[N];
    int ret = 0;
    Queue<Integer> 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();
        if (visited[pos] == 1)    continue;
        int x = stones[pos][0];
        int y = stones[pos][1];
        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;
  }
}
```

### Approach #1 DFS

Time: O(N^2) && Space: O(N^2)

```java
class Solution {
  public int removeStones(int[][] stones) {
        int N = stones.length;
    // graph[i][0] = the length of the 'list' graph[i][1:]
    int[][] graph = new int[N][N];
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
          graph[i][++graph[i][0]] = j; // ??
          graph[j][++graph[j][0]] = i; // ??
        }
      }
    }

    int ans = 0;
    boolean[] seen = new boolean[N];
    for (int i = 0; i < N; i++) {
      if (!seen[i]) {
        Stack<Integer> stack = new Stack();
        stack.push(i);
        seen[i] = true;
        ans--;
        while (!stack.isEmpty()) {
          int node = stack.pop();
          ans++;
          for (int k = 1; k <= graph[node][0]; k++) {
            int nei = graph[node][k];
            if (!seen[nei]) {
              stack.push(nei);
              seen[nei] = true;
            }
          }
        }
      }
    }

    return ans;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/union-find/947.most-stones-removed-with-same-row-or-column.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.