MediumRating 1565

3493. Properties Graph

arrayhash-tabledepth-first-searchbreadth-first-searchunion-findgraph

解題說明

Properties Graph

題目描述：給定 n 個節點，每個節點有一組屬性（整數陣列），以及一個整數 k。若兩個節點的屬性集合之間有至少 k 個共同屬性，則它們之間存在一條邊。求該圖中連通分量的數量。

解題思路：首先計算每對節點之間的共同屬性數量，可以用雜湊集合求交集。若交集大小 >= k，則將兩個節點合併。使用 Union-Find 資料結構來高效管理連通分量。遍歷所有 C(n,2) 對節點，對於每對計算共同屬性數並決定是否合併。最後統計不同根節點的數量即為答案。

C++ 解法

複雜度分析

時間複雜度：O(n² * p) — 其中 p 是每個節點的平均屬性數量。對 O(n²) 對節點計算交集，每次交集最多 O(p)。

空間複雜度：O(n * p) — 儲存每個節點的屬性集合。

虛擬碼

1. Initialize Union-Find with n nodes
2. For each node i, convert properties[i] to a hash set
3. For each pair (i, j) where i < j:
   a. Count common elements between sets[i] and sets[j]
   b. If common >= k, union(i, j)
4. Count distinct roots in Union-Find
5. Return the count of connected components

其他解法

DFS/BFS 建圖法：先建鄰接表（O(n²) 對每對節點判斷是否連邊），再用 DFS/BFS 計算連通分量。時間複雜度相同，但 Union-Find 實作更簡潔。

位元集合 (Bitset) 優化：若屬性值範圍有限，可用 bitset 表示每個節點的屬性集合，用 & 操作和 count() 快速計算交集大小。常數因子更小，適合屬性值域不大的情況。

延伸思考

如果 n 很大（10^5）且屬性很多，O(n²) 過慢，能否用 LSH (Locality Sensitive Hashing) 近似加速？
如果屬性可以動態增減，如何高效維護連通分量？
若改為「至少 k 個共同屬性或者存在某個特定屬性」的混合條件，該如何修改？

Properties Graph — CaffeCode