947-most-stones-removed-with-same-row-or-column.md

947. Most Stones Removed with Same Row or Column - 移除最多的同行或同列石头

在二维平面上，我们将石头放置在一些整数坐标点上。每个坐标点上最多只能有一块石头。

现在，move 操作将会移除与网格上的某一块石头共享一列或一行的一块石头。

我们最多能执行多少次 move 操作？

 

示例 1：

输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5

示例 2：

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3

示例 3：

输入：stones = [[0,0]]
输出：0

 

提示：

1. 1 <= stones.length <= 1000
2. 0 <= stones[i][j] < 10000

---

题目标签：Depth-first Search / Union Find

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	44 ms	34.6 MB

class UF {
public:
    vector<int> pre;
    UF(int n) {
        for (int i = 0; i < n; i++)
            pre.push_back(i);
    }
    
    int find(int x) {
        return pre[x] == x ? x : pre[x] = find(pre[x]);
    }
    
    void join(int x, int y) {
        int xr = find(x);
        int yr = find(y);
        if (xr != yr) {
            pre[xr] = yr;
        }
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        UF uf(20000);
        for (auto s : stones) {
            uf.join(s[0], s[1] + 10000);
        }
        unordered_set<int> conn;
        for (auto s : stones) {
            conn.insert(uf.find(s[0]));
        }
        return stones.size() - conn.size();
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();