2025-09-19：属性图用go语言，给出一个大小为 n×m 的整数矩阵 pro

摘要：2025-09-19：属性图。用go语言，给出一个大小为 n×m 的整数矩阵 properties 和一个整数 k。

2025-09-19：属性图。用go语言，给出一个大小为 n×m 的整数矩阵 properties 和一个整数 k。

定义一个函数，用来计算两个行向量之间不同元素的交集大小（即两行中共同出现的不重复整数的个数）。

把每一行看作图中的一个顶点，若任意两行之间共有的不同整数数目不少于 k，则在对应的两个顶点之间连一条无向边。

求该无向图中连通块（连通分量）的总数，并将该数作为结果返回。

输入： properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1。

输出： 3。

解释：

生成的图有 3 个连通分量：

题目来自力扣3493。

1. 问题理解：

• 给定一个 n x m 的矩阵 properties，其中每一行是一个属性集合（可能有重复元素）。

• 我们需要将每一行视为图中的一个顶点。

• 如果两行（即两个顶点）之间共同拥有的不同整数的个数（即交集大小）至少为 k，则在这两个顶点之间添加一条无向边。

• 最终目标是计算图中连通分量的数量。

2. 预处理每一行：

• 对于矩阵的每一行，我们需要去除重复元素（因为题目要求是“不同整数”的交集）。

• 创建一个长度为 n（行数）的切片 sets，其中每个元素是一个集合（这里用 map[int]bool 实现）。

• 遍历每一行 properties[i]，对于每个元素，将其添加到对应的集合 sets[i] 中。这样，sets[i] 就是第 i 行的不同整数集合。

3. 构建并查集（Union-Find）数据结构：

• 初始化一个并查集 u，大小为 n（即顶点数）。初始时每个顶点自成一个连通分量，所以连通分量数 cc 为 n。

• 并查集支持两种操作：

• find(x)：查找顶点 x 的根（代表元），同时进行路径压缩。

• merge(from, to)：合并两个顶点所在的集合（如果它们不在同一集合中），并减少连通分量计数cc。

4. 遍历所有行对，检查条件并合并：

• 对于每一对行 (i, j)（其中 i 从 0 到 n-1，j 从 0 到 i-1），计算它们的集合 sets[i] 和 sets[j] 的交集大小。

• 具体方法：遍历较小的集合（这里代码中固定遍历 sets[j]），检查每个元素是否在 sets[i] 中存在。统计存在的个数（即交集大小）。

• 如果交集大小 cnt >= k，则调用 u.merge(i, j) 合并这两个顶点（即合并它们所在的连通分量）。

5. 返回结果：

• 最终，并查集中的连通分量计数 u.cc 就是答案。

6. 示例分析（输入：properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k=1）：

• 预处理得到集合：

• 第0行: {1,2}

• 第1行: {1}

• 第2行: {3,4}

• 第3行: {4,5}

• 第4行: {5,6}

• 第5行: {7}

• 检查行对：

• (0,1): 交集{1}，大小=1>=1 → 合并。

• (0,2): 交集为空，不合并。

• ...（类似检查其他对）

• (2,3): 交集{4}，大小=1>=1 → 合并。

• (3,4): 交集{5}，大小=1>=1 → 合并（因此2,3,4合并成一个连通分量）。

• 其他对交集大小均小于1（或为空），不合并。

• 最终连通分量：

• 分量1：行0和行1（合并）

• 分量2：行2、3、4（合并）

• 分量3：行5（单独）

• 所以输出为3。

复杂度分析

• 时间复杂度：

预处理：遍历每行元素去重，每行最多 m 个元素（m遍历所有行对：共 O(n^2) 对（n对于每对，计算交集大小：需要遍历一个集合（大小最多为 m，即100），所以每对操作是 O(m)。因此总时间为 O(n*m + n^2 * m) = O(n^2 * m)。代入最大数值（n=100, m=100）约为100万次操作，在Go中是可接受的。

• 额外空间复杂度：

存储所有集合：n 个集合，每个集合最多 m 个元素，所以空间为 O(n*m)。并查集：O(n) 的父数组。总额外空间为 O(n*m)。package mainimport ( "fmt")type uf struct { fa int cc int}func newUnionFind(n int) uf { fa := make(int, n) for i := range fa { fa[i] = i } return uf{fa, n}}func (u uf) find(x int) int { if u.fa[x] != x { u.fa[x] = u.find(u.fa[x]) } return u.fa[x]}func (u *uf) merge(from, to int) { x, y := u.find(from), u.find(to) if x == y { return } u.fa[x] = y u.cc--}func numberOfComponents(properties int, k int)int { sets := make(map[int]bool, len(properties)) for i, a := range properties { sets[i] = map[int]bool{} for _, x := range a { sets[i][x] = true } } u := newUnionFind(len(properties)) for i, a := range sets { for j, b := range sets[:i] { cnt := 0 for x := range b { if a[x] { cnt++ } } if cnt >= k { u.merge(i, j) } } } return u.cc}func main { properties := int{{1, 2}, {1, 1}, {3, 4}, {4, 5}, {5, 6}, {7, 7}} k := 1 result := numberOfComponents(properties, k) fmt.Println(result)}

# -*-coding:utf-8-*-class UF: def __init__(self, n): self.fa = list(range(n)) self.cc = n def find(self, x): if self.fa[x] != x: self.fa[x] = self.find(self.fa[x]) return self.fa[x] def merge(self, from_, to): x = self.find(from_) y = self.find(to) if x == y: return self.fa[x] = y self.cc -= 1def number_of_components(properties, k): sets = for a in properties: sets.append(set(a)) n = len(properties) u = UF(n) for i in range(n): a = sets[i] for j in range(i): b = sets[j] cnt = len(a & b) # 计算交集大小 if cnt >= k: u.merge(i, j) return u.ccdef main: properties = [[1, 2], [1, 1], [3, 4], [4, 5], [5, 6], [7, 7]] k = 1 result = number_of_components(properties, k) print(result)if __name__ == "__main__": main