MediumRating 1375
1267. Count Servers that Communicate
arraydepth-first-searchbreadth-first-searchunion-findmatrixcounting
解題說明
Count Servers that Communicate
題目描述： 給定一個 m × n 的二維網格 grid，其中 1 代表伺服器，0 代表空位。如果兩台伺服器位於同一行或同一列，它們就可以通訊。請計算能夠與至少一台其他伺服器通訊的伺服器數量。
解題思路： 首先統計每一行和每一列中伺服器的數量。然後再次遍歷網格，對於每個伺服器位置 (i, j)，如果該行或該列的伺服器數量大於 1，則這台伺服器可以與其他伺服器通訊。這個方法利用了一個關鍵觀察：一台伺服器能通訊，當且僅當它所在的行或列至少有另一台伺服器。
C++ 解法
複雜度分析
時間複雜度：O(m × n) — 遍歷兩次網格，第一次統計行列伺服器數量，第二次統計可通訊的伺服器
空間複雜度：O(m + n) — 儲存每一行和每一列的伺服器計數
虛擬碼
1. Initialize rowCount[m] and colCount[n] to 0 2. First pass: for each cell (i, j) where grid[i][j] == 1, increment rowCount[i] and colCount[j] 3. Second pass: for each cell (i, j) where grid[i][j] == 1, if rowCount[i] > 1 OR colCount[j] > 1, increment result 4. Return result
其他解法
方法二：Union-Find（並查集） 將同一行或同一列的伺服器合併到同一個集合中，最後統計集合大小 > 1 的伺服器數量。時間複雜度 O(m × n × α(m × n))，空間複雜度 O(m × n)。相比計數法更複雜，但展示了圖論思維。
方法三：BFS/DFS 將每台伺服器視為節點，同行或同列的伺服器之間建立邊，用 BFS/DFS 找連通分量。大小 > 1 的連通分量中的所有伺服器都能通訊。時間空間複雜度較高，不推薦。
延伸思考
- 如果通訊條件改為「伺服器之間的曼哈頓距離不超過 k」，你會如何修改演算法？
- 如果網格非常稀疏（伺服器數量遠小於 m × n），如何優化空間和時間？
- 如果需要輸出所有通訊群組（每個群組包含互相可達的伺服器），你會使用什麼資料結構？