947. Most Stones Removed with Same Row or Column

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

二维坐标系有给定的一些点，每次能从有相同横坐标或纵坐标的点中移除一个点，问最多能移除几个点。同行或同列的组成了一个联通图，每个点会被包含在同行或同列的一个联通图中。如果有个方案能让每个联通子图的所有结点除了最后一个外全删掉，那删掉的数目就是最优解，也就是总点数-独立联通子图数。可以证明这个方案是存在的，逆着来看，把任意一点当作最后剩下的那个点，从这个点开始对四周做DFS，都可以遍历到UF内其它任意点。

算二维联通子图数目有个小技巧，把Y坐标和X区分开(X upper limit后)后放在一维里。

/*
 * @lc app=leetcode id=947 lang=cpp
 *
 * [947] Most Stones Removed with Same Row or Column
 */

// @lc code=start
class Solution {
public:
class UF {
public:
    vector<int> parents;
    UF(int N): parents(N) {
        for (int i = 0; i < N; ++i) {
            parents[i] = i;
        }
    }
    int find(int x) {
        while (x != parents[x]) {
            x = parents[x];
            parents[x] = parents[parents[x]];
        }
        return parents[x];
    }

    void un(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) parents[x] = y;
    }
};
    int removeStones(vector<vector<int>>& stones) {
        const int k_size = 10000;
        UF uf(k_size * 2);
        for (const auto &s : stones) {
            uf.un(s[0], s[1] + k_size);
        }
        unordered_set<int> visited;
        for (const auto &s : stones) {
            visited.insert(uf.find(s[0]));
        }
        return stones.size() - visited.size();
    }
};
// @lc code=end