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:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation: One way to remove 5 stones is as follows:
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.

My Solutions:

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

Example 3:

Input: stones = [[0,0]]
Output: 0
Explanation: [0,0] is the only stone on the plane, so you cannot remove it.

x/rootX: 10000/10000; y/rootY: 0/0

key = 10000; value = 0

key = 0; value = 0

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Explanation: One way to make 3 moves is as follows:
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.

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

key = 0; value = 2

key = 10001; value = 1

key = 1; value = 1

key = 2; value = 2

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();
    }
}