947. Most Stones Removed with Same Row or Column

might say Lee's explanation is the best for this Q

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/solutions/197668/count-the-number-of-islands-o-n/

but he uses ~ , for O(n) processing, digest later

T: O(n^2)??? -> should O(N⋅α(K))

S: O(n)

```java
class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        UnionFind uf = new UnionFind(n);

        // 2D to 1D corodinate and map to node id (0~n-1) 
        Map<Integer, Integer> nodeIdMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            nodeIdMap.put(encode(stones[i][0], stones[i][1]), i);
        }

        // row, col has elements, record x -> has many 1D(x,y), y -> has many 1D(x,y)
        Map<Integer, List<Integer>> rowPointMap = new HashMap<>();
        Map<Integer, List<Integer>> colPointMap = new HashMap<>();
        for (int[] stone : stones) {
            int x = stone[0];
            int y = stone[1];
            rowPointMap.putIfAbsent(stone[0], new ArrayList<>());
            rowPointMap.get(stone[0]).add(encode(x, y));

            colPointMap.putIfAbsent(stone[1], new ArrayList<>());
            colPointMap.get(stone[1]).add(encode(x, y));
        }

        // union all stone by row
        for (int rowKey : rowPointMap.keySet()) {
            List<Integer> list = rowPointMap.get(rowKey);
            int firstId = nodeIdMap.get(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                int nextId = nodeIdMap.get(list.get(i));
                uf.union(firstId, nextId);
            }
        }
        // union all stone by col
        for (int colKey : colPointMap.keySet()) {
            List<Integer> list = colPointMap.get(colKey);
            int firstId = nodeIdMap.get(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                int nextId = nodeIdMap.get(list.get(i));
                uf.union(firstId, nextId);
            }
        }
        // total stone number - component number
        return n - uf.getComponentsCount();
    }
    private int encode(int x, int y) {
        return x*10000 + y;
    }
    
    class UnionFind {
        int[] parent;
        int count;
        UnionFind(int n) {
            this.count = n;
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        public boolean union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                parent[x] = y;
                this.count--;
                return true;
            }
            return false;
        }
        private int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        private int getComponentsCount() {
            return this.count;
        }
    }
}
/*
[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]


o o x
o x o 
o x o

so key is we can use row and col to make
stone connected

and in one component, at last we'll leave one stone

so how many stone can be eliminated: total stone number - component number
so ex1: 6 - 1 = 5

how to connect by row and col? use union find
but this one is 2D array, so we'll use 2D to 1D skill to note which node mapping to xy
xy -> node id
*/
```

其實不需要 1d 對應...

直接對應 0 ~ n-1 node 編號即可..

T: O(N⋅α(K))

S: O(n)

```java
class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        UnionFind uf = new UnionFind(n);
        Map<Integer, List<Integer>> rowMap = new HashMap<>();
        Map<Integer, List<Integer>> colMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int x = stones[i][0];
            int y = stones[i][1];
            rowMap.putIfAbsent(x, new ArrayList<>());
            rowMap.get(x).add(i);

            colMap.putIfAbsent(y, new ArrayList<>());
            colMap.get(y).add(i);
        }
        for (int key : rowMap.keySet()) {
            List<Integer> nodeIdList = rowMap.get(key);
            int firstNodeId = nodeIdList.get(0);
            for (int i = 1; i < nodeIdList.size(); i++) {
                uf.union(firstNodeId, nodeIdList.get(i));
            }
        }
        for (int key : colMap.keySet()) {
            List<Integer> nodeIdList = colMap.get(key);
            int firstNodeId = nodeIdList.get(0);
            for (int i = 1; i < nodeIdList.size(); i++) {
                uf.union(firstNodeId, nodeIdList.get(i));
            }
        }

        return n - uf.getComponentCount();
    }
    class UnionFind {
        private int[] parent;
        private int count;
        UnionFind(int n) {
            this.parent = new int[n];
            this.count = n;
            for (int i = 0; i < n ; i++) {
                this.parent[i] = i;
            }
        }
        public boolean union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                parent[x] = y;
                count--;
                return true;
            }
            return false;
        }
        public int getComponentCount() {
            return this.count;
        }
        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}
```