Python实现：基于节点对分组指定连通节点的方法咨询

核心思路 #

用**并查集（Union-Find）**数据结构处理节点连通关系，这是解决这类连通分量分组问题的高效方案，能快速合并连通节点并查找节点所属的连通根。

实现代码 #

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    def find(self, x):
        # 路径压缩优化，让节点直接指向根节点
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 初始化节点父节点为自身
        if x not in self.parent:
            self.parent[x] = x
        if y not in self.parent:
            self.parent[y] = y
        # 合并两个节点的连通分量
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

# 给定输入
pairs = [[0,10],[0,1],[0,2],[1,7],[2,3],[2,4],[3,8],[4,5],[5,6],[8,9]]
a = [3,4,5,6,8,9]

# 初始化并查集
uf = UnionFind()
# 遍历节点对，构建连通关系
for u, v in pairs:
    uf.union(u, v)

# 按连通根节点分组
groups = {}
for node in a:
    root = uf.find(node)
    if root not in groups:
        groups[root] = []
    groups[root].append(node)

# 转换为要求的列表格式
result = list(groups.values())
print(result)  # 输出: [[3,8,9],[4,5,6]]

代码说明 #

• UnionFind类：
  • parent字典存储每个节点的父节点，初始时节点的父节点是自身。
  • find方法通过路径压缩优化，减少后续查找的时间开销。
  • union方法将两个节点所在的连通分量合并，确保同一连通分量的节点共享同一个根。
• 构建连通关系：遍历所有节点对，调用union方法把连通的节点合并。
• 分组节点：遍历列表a中的每个节点，找到其连通根，将节点归类到对应根的分组中，最后提取分组结果。

内容的提问来源于stack exchange，提问作者ying zhang