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.

&nbsp;
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.


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.


Example 3:

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


&nbsp;
Constraints:


	1 &lt;= stones.length &lt;= 1000
	0 &lt;= xi, yi &lt;= 104
	No two stones are at the same coordinate point.


class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        def dfs(row,col):
            if seen[(row,col)]:
                return 0
            seen[(row,col)] = True
            for r,c in tableRow[row]:
                dfs(r,c)
            for r,c in tableCol[col]:
                dfs(r,c)
            return 1

        tableRow, tableCol = {},{}
        for row,col in stones:
            if row not in tableRow:
                tableRow[row] = set()
            if col not in tableCol:
                tableCol[col] = set()
            tableRow[row].add((row,col))
            tableCol[col].add((row,col))

        count,seen= 0, {(row,col):False for row,col in stones}
        for row,col in stones:
            count += dfs(row,col)
        return abs(len(stones)-count)
class Solution {
    public int removeStones(int[][] stones) {
        int ret=0;
        DisjointSet ds=new DisjointSet(stones.length);

        for(int i=0;i<stones.length;i++) {
            for(int j=i+1;j<stones.length;j++) {
                int s1[]=stones[i];
                int s2[]=stones[j];

                if(s1[0]==s2[0] || s1[1]==s2[1]) {
                    ds.union(i, j);
                }
            }
        }
        // System.out.println(Arrays.toString(ds.sets));
        for(int i=0;i<ds.sets.length;i++) {
            if(ds.sets[i]<0)
                ret+=Math.abs(ds.sets[i])-1;
        }

        return ret;
    }

    class DisjointSet {
        public int sets[];

        public DisjointSet(int size) {
            sets=new int[size];
            Arrays.fill(sets, -1);
        }

        //
        // weighted union
        //union->return size in negative
        public int union(int idx1, int idx2) {
            int p1=find(idx1);
            int p2=find(idx2);

            if(p1==p2) { //same parent so directly returning size
                return sets[p1];
            }else {
                int w1=Math.abs(sets[p1]);
                int w2=Math.abs(sets[p2]);

                if(w1>w2) {
                    sets[p2]=p1;

                    //collapsing FIND
                    sets[idx1]=p1;
                    sets[idx2]=p1;

                    return sets[p1]=-(w1+w2);
                }else {
                    sets[p1]=p2;

                    //collapsing FIND
                    sets[idx1]=p2;
                    sets[idx2]=p2;

                    return sets[p2]=-(w1+w2);
                }
            }
        }

        // collapsing FIND
        //find parent
        public int find(int idx) {
            int p=idx;
            while(sets[p]>=0) {
                p=sets[p];
            }
            return p;
        }
    }
}
class Solution {
    class UnionFind 
    {
        vector<int> parent, rank;
        public:
        int count = 0;
        UnionFind(int n)
        {
            count = n;
            parent.assign(n, 0);
            rank.assign(n, 0);
            for(int i=0;i<n;i++)
            {
                parent[i] = i;
            }
        }
        int find(int p)
        {
            while(p!=parent[p])
            {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }
        bool Union(int p, int q)
        {
            int rootp = find(p);
            int rootq = find(q);
            if(rootp == rootq)
                return false;
            else if(rank[rootp] < rank[rootq])
            {
                parent[rootp] = rootq;
                rank[rootq]++;
                count--;
                return true;
            }
            else
            {
                parent[rootq] = rootp;
                rank[rootp]++;
                count--;
                return true;
            }
        }
    };
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        UnionFind uf(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1])
                    uf.Union(i,j);
            }
        }

        return n - uf.count;
    }
};
/**
 * @param {number[][]} stones
 * @return {number}
 */
var removeStones = function(stones) {
    
    const n = stones.length
    // initial number of components(a.k.a island)
    let numComponents = n
    
    //initial forest for union find
    let forest = new Array(n).fill(0).map((ele, index) => index)

    // recursively finding the root of rarget node
    const find = (a) => {
        if(forest[a] === a) {
            return a
        }
        return find(forest[a])
    }
    
    // function for uniting two stones
    const union = (a, b) => {
        const rootA = find(a)
        const rootB = find(b)
        if(rootA != rootB) {
            //connect their roots if currently they are not connected
            forest[rootA] = rootB
            //subtract the number of islands by one since two islands are connected now
            numComponents -= 1
        }
    }
    
    for(let i = 0; i < stones.length - 1; i++) {
        for(let j = i + 1; j < stones.length; j++) {
            // if two stones are connected(i.e. share same row or column), unite them
            if(stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1]) {
                union(i, j)
            }
        }
    }

    // this is the most confusing part.
    // The number of stones can be removed is not equal to the number of islands.
    // e.g. we have two islands with total of 10 stores, each island will leave one extra stone after the 
    // removal, therefore we can remove 10 - 2 = 8 stones in total
    return n - numComponents
};
Most Stones Removed with Same Row or Column