947. Most Stones Removed with Same Row or Column

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. 1 <= stones.length <= 1000
2. 0 <= stones[i][j] < 10000

-----------------------
类似find number of islands。本题对小岛的定义是同行同列有相同的石头就是一个岛。一个小岛最多能被切割size －1次。所以只要遍历所有小岛就可以。

union find的做法。对小岛的查找只要row或col相同就属于一个岛
O(m * n) time

class Solution {
    public int removeStones(int[][] stones) {
        Map<Integer, Integer> rows = new HashMap<>();
        Map<Integer, Integer> cols = new HashMap<>();
        Map<Integer, Integer> ids = new HashMap<>();
        Map<Integer, Integer> sizes = new HashMap<>();
        
        int id = 0;
        for (int[] stone : stones) {
            int addi = 1;
            if (!rows.containsKey(stone[0])) {
                rows.put(stone[0], id);
                ids.put(id, id);
                sizes.put(id, addi);
                id++;
                addi = 0;
            }
            if (!cols.containsKey(stone[1])) {
                cols.put(stone[1], id);
                ids.put(id, id);
                sizes.put(id, addi);
                id++;
                addi = 0;
            }

            int rowRoot = findRoot(rows.get(stone[0]), ids);
            int colRoot = findRoot(cols.get(stone[1]), ids);
            if (rowRoot != colRoot) {
                if (sizes.get(colRoot) > sizes.get(rowRoot)) {
                    ids.put(rowRoot, colRoot);
                    sizes.put(colRoot, sizes.get(colRoot) + sizes.get(rowRoot) + addi);
                    rows.put(stone[0], colRoot);
                    cols.put(stone[1], colRoot);
                }else {
                    ids.put(colRoot, rowRoot);
                    sizes.put(rowRoot, sizes.get(colRoot) + sizes.get(rowRoot) + addi);
                    rows.put(stone[0], rowRoot);
                    cols.put(stone[1], rowRoot);
                }
            }else {
                sizes.put(rowRoot, sizes.get(rowRoot) + addi);
            }
            
        }
        
        int size = 0;
        Set<Integer> iddd = new HashSet<>();
        for (int i : ids.values()) {
            iddd.add(findRoot(i, ids));
        }
        
        for (int i : iddd) {
            size += sizes.get(i) - 1;
        }
        
        return size;
    }
    
    private int findRoot(int p, Map<Integer, Integer> ids) {
        while (ids.get(p) != p) {
            ids.put(p, ids.get(ids.get(p)));
            p = ids.get(p);
        }
        
        return p;
    }
}