Leetcode 947: Most Stones Removed with Same Row or Column

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/description/

Notes:

This question is equivalent to find the number of group of the "connected" points.

For each group, we can take all the stones except the last one. So the maximum number of stones that can be picked up is Total - numGroup.

Here, "connected" means the points have at least the same x or (or and) y. This can be solved by dfs or bfs after building a graph which contains the connecting information.

A union-find algorithm can also be used to this question.

For this question, we need to distinguish x and y. So we may use two unordered_maps (or other tricks, for example, adding y by 10000).

There are three cases:

1): if both x and y are not found before, it means it is a new group;

2): if one of the x and y (x or y, not both) has been labeled, it means this points must connect to a previous group;

3): if both x and y are found, there are two sub-cases:
       a): x and y belongs to the same group (same root or parent), it is the same as the above case 2);
       b): if not the same group, then this point connects two previous groups together. So we need to reduce the group number by one.

The terminal condition for the find() in the Union-find algorithm is that p(x) == x, so we can set the root or parent up in the beginning.

 See the code below:

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size(), numGp = n;
        unordered_map<int, int> px, py;
        for(int i=1; i<=n; ++i) {//initilize the roots or parents
            px[-i] = -i;
            py[-i] = -i;
        }
        for(int i=1; i<=n; ++i) {//find number of groups
            int x = stones[i-1][0], y = stones[i-1][1];
            if(!px.count(x) && !py.count(y)) {
                px[x] = -i;
                py[y] = -i;
            }
            else {
                --numGp; //the new stone must connecte to at least one existing group, or two groups.
                if(!px.count(x)) {
                    int ry = find(y, py);
                    px[x] = ry;
                }
                else if(!py.count(y)) {
                    int rx = find(x, px);
                    py[y] = rx;
                }
                else {
                    int rx = find(x, px), ry = find(y, py);
                    if(rx != ry) {//connect two groups
                        --numGp;
                        px[ry] = rx;
                        py[ry] = rx;
                    }
                }
            }
        }
        return n - numGp;
    }
private:
    int find(int x, unordered_map<int, int>& mp) {
        if(mp[x] != x) mp[x] = find(mp[x], mp);
        return mp[x];
    }
};

Another implementation which is more general, or like a template.

See the code below:

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        numGroup = 0;//initialization
        for(auto &a : stones) {
            unite(a[0], -a[1]-1);//need to distinguish x and y
        }
        return n - numGroup;
    }

private:
    unordered_map<int, int> mp;
    int numGroup;

    int find(int x) {
        if(!mp.count(x)) {
            mp[x] = x;
            ++numGroup;
        }
        if(mp[x] != x) mp[x] = find(mp[x]);
        return mp[x];
    }

    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if(rx != ry) {
            mp[rx] = ry;
            --numGroup;
        }
    }
};