MediumRating 1899

947. Most Stones Removed with Same Row or Column

hash-tabledepth-first-searchunion-findgraph

在 LeetCode 上作答 ↗

解題說明

Most Stones Removed with Same Row or Column

題目描述：在一個無限二維平面上放有若干顆石頭（每格最多一顆）。每次可以移除一顆石頭，條件是它所在的行或列上還有至少另一顆石頭。求最多能移除幾顆石頭。

解題思路：

關鍵洞察：若一組石頭形成一個連通分量（透過行/列相連），則這組石頭中只有最後一顆無法被移除（因為它是該分量中唯一剩下的石頭，行和列都沒有其他石頭了）。因此，每個連通分量最多可移除（分量大小 - 1）顆石頭。

答案公式：n - 連通分量數量，其中 n 為石頭總數。

Union-Find 設計技巧：

同一行的石頭可以相互連接，同一列的石頭也可以相互連接。
直接用行號和列號作為 Union-Find 節點，但行號和列號的範圍都在 [0, 10000]，需要區分：
- 行節點：索引 r
- 列節點：索引 c + 10001（偏移避免衝突）
每顆石頭 (r, c) 執行 union(r, c + 10001)，將其所在行和列連接起來。
最後統計「有石頭涉及的」不同根節點數量，即連通分量數。

計數方法：只統計實際出現過的行/列節點中不同根的數量（用 unordered_set 收集所有出現過的節點的根）。

C++ 解法

複雜度分析

時間複雜度：O(n · α(n)) ≈ O(n) — 對 n 顆石頭各執行一次 union（O(α(n))）和一次 find，整體接近線性。

空間複雜度：O(n) — parent 雜湊表最多儲存 2n 個節點（每顆石頭貢獻一個行節點和一個列節點）；roots 集合最多 n 個元素。

虛擬碼

1. Initialize parent as empty hash map (lazy initialization)
2. For each stone (r, c):
   unite(r, c + 10001)  // connect row-node and col-node
3. Initialize empty set 'roots'
4. For each stone (r, c):
   roots.insert(find(r))  // find root of this stone's row-node
5. Return n - roots.size()  // stones removable = total - components

find(x):
  If x not in parent: parent[x] = x
  If parent[x] != x: parent[x] = find(parent[x])  // path compress
  Return parent[x]

unite(a, b):
  ra = find(a), rb = find(b)
  If ra != rb: parent[ra] = rb

其他解法

DFS 建圖 O(n²)：對所有石頭對，若同行或同列則建邊，再用 DFS/BFS 統計連通分量數。優點是思路直觀；缺點是建圖需要 O(n²) 時間（n 最大 1000，約 10⁶），且需要額外 O(n²) 空間存邊。相比 Union-Find 的 O(n) 方法明顯較慢。

雜湊表分組 + DFS O(n)：用兩個雜湊表分別將同行和同列的石頭分組，再用 DFS/BFS 沿行/列連接計算連通分量。優點是不需要 offset 技巧，更直觀；缺點是需要兩個雜湊表加上 visited 陣列，常數略大，但時間複雜度同為 O(n)。

陣列版 Union-Find（固定大小）：因為行/列座標最大為 10000，可以預先分配大小為 20002 的陣列（行 0-10000，列 10001-20001），避免雜湊表的 overhead。優點是存取速度快（O(1) 陣列存取 vs 雜湊表）；缺點是固定分配 20002 個整數的空間，當 n 很小時相對浪費。實際測試中此版本通常比雜湊表版更快。

延伸思考

若座標範圍從 10000 擴大到 10⁹，使用陣列版 Union-Find 會 MLE，本題的雜湊表方案是否仍然適用？還有什麼更好的空間優化方法？
若允許對角線相鄰（即同一斜線上的石頭也可以互相移除），Union-Find 的節點設計需要如何調整？
本題最終答案 n - components 的推導基於「每個連通分量恰好留 1 顆」，請證明任何連通分量都能達到這個最優值（即一定存在合法的移除順序讓分量僅剩 1 顆）。

解題說明

Most Stones Removed with Same Row or Column

解題思路：

答案公式：n - 連通分量數量，其中 n 為石頭總數。

Union-Find 設計技巧：

同一行的石頭可以相互連接，同一列的石頭也可以相互連接。
直接用行號和列號作為 Union-Find 節點，但行號和列號的範圍都在 [0, 10000]，需要區分：
- 行節點：索引 r
- 列節點：索引 c + 10001（偏移避免衝突）
每顆石頭 (r, c) 執行 union(r, c + 10001)，將其所在行和列連接起來。
最後統計「有石頭涉及的」不同根節點數量，即連通分量數。

計數方法：只統計實際出現過的行/列節點中不同根的數量（用 unordered_set 收集所有出現過的節點的根）。

虛擬碼

1. Initialize parent as empty hash map (lazy initialization) 2. For each stone (r, c): unite(r, c + 10001) // connect row-node and col-node 3. Initialize empty set 'roots' 4. For each stone (r, c): roots.insert(find(r)) // find root of this stone's row-node 5. Return n - roots.size() // stones removable = total - components find(x): If x not in parent: parent[x] = x If parent[x] != x: parent[x] = find(parent[x]) // path compress Return parent[x] unite(a, b): ra = find(a), rb = find(b) If ra != rb: parent[ra] = rb

其他解法

延伸思考

若座標範圍從 10000 擴大到 10⁹，使用陣列版 Union-Find 會 MLE，本題的雜湊表方案是否仍然適用？還有什麼更好的空間優化方法？
若允許對角線相鄰（即同一斜線上的石頭也可以互相移除），Union-Find 的節點設計需要如何調整？
本題最終答案 n - components 的推導基於「每個連通分量恰好留 1 顆」，請證明任何連通分量都能達到這個最優值（即一定存在合法的移除順序讓分量僅剩 1 顆）。