<p>On a 2D plane, we place <code>n</code> stones at some integer coordinate points. Each coordinate point may have at most one stone.</p>

<p>A stone can be removed if it shares either <strong>the same row or the same column</strong> as another stone that has not been removed.</p>

<p>Given an array <code>stones</code> of length <code>n</code> where <code>stones[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> represents the location of the <code>i<sup>th</sup></code> stone, return <em>the largest possible number of stones that can be removed</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
<strong>Output:</strong> 5
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= stones.length &lt;= 1000</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li>No two stones are at the same coordinate point.</li>
</ul>

class Solution {
public:
    // find with path compression
    int find(int u, vector<int> &parent){
        if(parent[u] == u){
            return u;
        }
        return parent[u] = find(parent[u], parent);
    }

    // union (by rank, attach smaller set into bigger set.)
    void performUnion(int u, int v, vector<int> &parent, vector<long> &treeSize){
        int parentU = find(u, parent);
        int parentV = find(v, parent);
        int sizeU = treeSize[parentU], sizeV = treeSize[parentV];
        if(sizeU < sizeV){
            parent[parentU] = parentV;
            treeSize[parentV] += sizeU;
        }
        else{
            parent[parentV] = parentU;
            treeSize[parentU] += sizeV;
        }
    }

    int removeStones(vector<vector<int>>& stones) {
        // MAKE-SET 
        vector<int> parent(stones.size(), -1);
        vector<long> treeSize(stones.size(), 1);
        for(int i = 0; i < stones.size(); i++){
            parent[i] = i;
        }
        // UNION(u, v) 
        for(int i = 0; i < stones.size(); i++){
            for(int j = i+1; j < stones.size(); j++){
                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]){
                    // same row or column -> edge.
                    performUnion(i, j, parent, treeSize);
                }
            }
        }

        // FIND(u)
        int ans = 0; 
        for(int i = 0; i < stones.size(); i++){
            ans += parent[i] != i;
        }
        return ans; 
    }
};

/*
    Observation:
        1) We are eventually creating groups, which we can create using DSU in O(N).
        2) To get numNodes under each parent, we can simply count all nodes who aren't parent of themselves.
        3) Hence, overall time complexity & Space complexity of algorithm = O(N).

    DSU Steps: 
    1) Make Set -> sets having only 1 element and the representative element is the element itself.
    2) Union(u, v) -> given u and v has an edge b/w them, in our case, edge will be there if in same row/col. 
    3) To get the ans, run find(u) across all again and count += (element != representative element).
*/
18421