• Leetcode 3493. Properties Graph
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3493. Properties Graph

1. 解题思路

这一题的话是要考虑最终聚合的簇的个数，因此很明显就是一个并查集的典型题目。因此，我们只需要创建一个并查集，然后两两考察其各自的关联关系即可。

而关于并查集的相关内容，网上已经有很多了，我自己也有一篇拙作（经典算法：并查集（DSU）结构简介）来作备忘。所以这里就不过多展开了，有兴趣的读者可以自行了解一下相关的内容。

2. 代码实现

给出python代码实现如下：

class DSU:def __init__(self, N):self.root = [i for i in range(N)]def find(self, k):if self.root[k] != k:self.root[k] = self.find(self.root[k])return self.root[k]def union(self, a, b):x = self.find(a)y = self.find(b)if x != y:self.root[y] = xreturnclass Solution:def numberOfComponents(self, properties: List[List[int]], k: int) -> int:elems = [set(x) for x in properties]n = len(properties)dsu = DSU(n)for i in range(n-1):for j in range(i+1, n):intersect = len(elems[i] & elems[j])if intersect >= k:dsu.union(i, j)clusters = [dsu.find(i) for i in range(n)]return len(set(clusters))

提交代码评测得到：耗时206ms，占用内存18.7MB。