# 947. Most Stones Removed with Same Row or Column

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

A stone can be removed if it shares either **the same row or the same column** as another stone that has not been removed.

Given an array `stones` of length `n` where `stones[i] = [xi, yi]` represents the location of the `ith` stone, return *the largest possible number of stones that can be removed*.

**Example 1:**

<pre><code><strong>Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
</strong><strong>Output: 5
</strong><strong>Explanation: One way to remove 5 stones is as follows:
</strong>1. Remove stone [2,2] because it shares the same row as [2,1].
2. Remove stone [2,1] because it shares the same column as [0,1].
3. Remove stone [1,2] because it shares the same row as [1,0].
4. Remove stone [1,0] because it shares the same column as [0,0].
5. Remove stone [0,1] because it shares the same row as [0,0].
Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.
</code></pre>

***My Solutions:***

用union find的思想来做。所有的坐标如果x或者y相同则结合成一个set，这道题是在找可以组成几个unique set，结果是stones的数量减去set。对一个点（x,y）来说，find到点的x,y坐标的root，然后union起来。

**Example 3:**

<pre><code><strong>Input: stones = [[0,0]]
</strong><strong>Output: 0
</strong><strong>Explanation: [0,0] is the only stone on the plane, so you cannot remove it.
</strong></code></pre>

x/rootX: 10000/10000; y/rootY: 0/0&#x20;

key = 10000; value = 0&#x20;

key = 0; value = 0

**Example 2:**

<pre><code><strong>Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
</strong><strong>Output: 3
</strong><strong>Explanation: One way to make 3 moves is as follows:
</strong>1. Remove stone [2,2] because it shares the same row as [2,0].
2. Remove stone [2,0] because it shares the same column as [0,0].
3. Remove stone [0,2] because it shares the same row as [0,0].
Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.
</code></pre>

x/rootX: 10000/10000; y/rootY: 0/0 --> 对应点(10000,0)

x/rootX: 10000/0; y/rootY: 2/2 -> 对应点(0,2)

x/rootX: 10001/10001; y/rootY: 1/1 -> 对应点(10001,1)

x/rootX: 10002/10002; y/rootY: 0/2 -> 对应点(10002,2)

x/rootX: 10002/2; y/rootY: 2/2 -> 对应点(2,2)

key = 10000; value = 0&#x20;

key = 0; value = 2&#x20;

key = 10001; value = 1&#x20;

key = 1; value = 1&#x20;

key = 2; value = 2&#x20;

key = 10002; value = 2

```
class Solution {

    class UnionFind {
        Map<Integer, Integer> roots;
        int count;

        public UnionFind() {
            roots = new HashMap<>();
            count = 0;
        }

        public int getCount() { return count; }
        public Map<Integer, Integer> getRoots() { return roots; }

        public int find(int coor) {
            if (!roots.containsKey(coor)) {
                roots.put(coor, coor);
                count++;
            }
            // 这一步不可省略，因为要用来count++
            if (coor != roots.get(coor)) roots.put(coor, find(roots.get(coor)));
            return roots.get(coor);
        }

        public void union(int x, int y) {
            int rootX = find(x), rootY = find(y);

            System.out.println("x/rootX: " + x + "/" + rootX + "; y/rootY: " + y + "/" + rootY);
            
            if (rootX != rootY) {
                roots.put(rootX, rootY);
                count--;
            }
        }
    }
    public int removeStones(int[][] stones) {
        int n = stones.length;
        UnionFind uf = new UnionFind();
        for (int[] edge : stones) {
            // By using the magic number 10000, we place our found x values outside of the bounds of the problem. This way, any y values we find will not conflict with x values.
            uf.union(edge[0] + 10000, edge[1]);
        }

        for (Map.Entry<Integer, Integer> element : uf.getRoots().entrySet()) {
            System.out.println("key = " + element.getKey() + "; value = " + element.getValue());
        }

        return n - uf.getCount();
    }
}
```
