Medium
Related Topics: Hash Table / Depth-First Search / Union Find / Graph
LeetCode Source

解題想法

首先，程式碼定義了兩個重要的變數 M 和 N。

其中 M 是一個大於石頭座標的最大值，而 N 是 2*M+1，這是為了確保可以在同一個數組中處理行和列兩個維度。

接著，初始化了一個列表 root，用來記錄每個節點的根節點，還有一個列表 Size，用來記錄每個連通分量的大小。

Find 函數是用來找到某個節點的根節點，並壓縮路徑以加快後續的查找速度；Union 函數則是用來合併兩個節點所在的集合，如果這兩個節點原本不在同一個集合中，則更新連通分量的大小並增加合併計數 merge。

程式碼遍歷了所有石頭的位置，並通過 Union 函數將行和列的關係連接起來。

最後，通過計算連接成功的次數和未連接的行或列數量，得到可以移除的石頭數量。

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Python

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n, M=len(stones), 10001
        N=2*M+1
        root=list(range(N))
        Size=[1]*N
        merge=0

        def Find(x):
            if x==root[x]: return x
            root[x]=Find(root[x])
            return root[x]
        
        def Union(x, y):
            nonlocal merge
            x, y=Find(x), Find(y)
            if x==y: return False
            if Size[x]>Size[y]:
                Size[x]+=Size[y]
                root[y]=x
            else:
                Size[y]+=Size[x]
                root[x]=y
            merge+=1
            return True
        cntRC=[False]*N
        for i, j in stones:
            Union(i, M+j)
            cntRC[i]=cntRC[M+j]=True
        return n-cntRC.count(True)+merge

C++

class Solution {
public:    
    int removeStones(vector<vector<int>>& stones) {
        const int n = stones.size(), M=10001, N=2*M+1;
        UnionFind G(N);
        bitset<20003> cntRC=0;
        for (int idx = 0; idx < n; idx++) {
            const int i = stones[idx][0], j=stones[idx][1];
            G.Union(i, M+j);// connect row[i] & col[j]
            cntRC[i]=cntRC[M+j]=1;
        }
        return n-cntRC.count()+G.merge;
    }
};
 
auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();