Most Stones Removed

Given a matrix of integers A of size N x 2 describing coordinates of N stones placed in 2D plane.
Now, a move consists of removing a stone that shares a column or row with another stone on the plane.

Find and return the largest number of moves you can make.

Note: Each of the N coordinate points contains exactly one stone.

The first argument given is the integer matrix A.

Return the largest number of moves you can make.

1 <= N <= 100000
0 <= A[i][0], A[i][1] <= 10000

Input 1:
    A = [   [0, 0]
            [0, 1]
            [1, 0]
            [1, 2]
            [2, 2]
            [2, 1]   ]
Output 1:
    5
Explanation 1:
    One of the order of removing stones:
    1. Remove (2,1) as it shares row with (2,2)
        remaining stones ( (0,0), (0,1), (1,0), (1,2) and (2,2)).
    2. Remove (2,2) as it shares column with (1,2)
        remaining stones ( (0,0), (0,1), (1,0) and (1,2)).
    3. Remove (0,1) as it shares row with (0,0)
        remaining stones ( (0,0), (1,0) and (1,2)).
    4. Remove (1,2) as it shares row with (1,0)
        remaining stones ( (0,0) and (1,0)).
    5. Remove (0,0) as it shares column with (1,0)
        remaining stones ((1,0)).
   So the maximum number of moves is 5.
    
Input 2:
    A = [   [0, 0]
            [0, 2]
            [2, 0]
            [1, 1]
            [2, 2]   ]
Output 2:
    3

Solution:

Time: O(n^2)

public class Solution {
    static class UF {
        private int count;
        private int[] parent;
        private int[] size;
        
        public UF(int n) {
            this.count = n;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i ++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        public int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        
        public int[] size() { return size; }
        public int[] parent() { return parent; }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            if (size[rootX] <= size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
            count --;
        }
        
        public int count() { return count; }
    }
    
    public int solve(ArrayList<ArrayList<Integer>> A) {
        int n = A.size();
        UF stones = new UF(n);
        for (int i = 0; i < n; i ++) {
            for (int j = i + 1; j < n; j ++) {
                ArrayList<Integer> stone1 = A.get(i);
                ArrayList<Integer> stone2 = A.get(j);
                if (stone1.get(0) == stone2.get(0) || stone1.get(1) == stone2.get(1)) {
                    stones.union(i, j);
                }
            }
        }
        int max = 0;
        for (int i = 0; i < n; i ++) {
            if (stones.parent()[i] != i) continue;
            int val = stones.size()[i];
            if (val >= 2) {
                max += val - 1;
            }
        }
        return max;
    }
}

Solution2:

Time: O(n)

public class Solution {
    static class UF {
        private int count;
        private int[] parent;
        private int[] size;
        
        public UF(int n) {
            this.count = n;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i ++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        public int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        
        public int[] size() { return size; }
        public int[] parent() { return parent; }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            if (size[rootX] <= size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
            count --;
        }
        
        public int count() { return count; }
    }
    
    public int solve(ArrayList<ArrayList<Integer>> A) {
        int n = A.size();
        UF stones = new UF(20001);
        for (int i = 0; i < n; i ++) {
            ArrayList<Integer> stone = A.get(i);
            stones.union(stone.get(0), stone.get(1) + 10000);
        }
        Set<Integer> remain = new HashSet<>();
        for (int i = 0; i < n; i ++) {
            ArrayList<Integer> stone = A.get(i);
            int val1 = stones.size()[stones.find(stone.get(0))];
            remain.add(stones.find(stone.get(0)));
        }
        return n - remain.size();
    }
}