基于秩和路径压缩的数据库表合并问题Bug排查求助

核心Bug分析 #

你的代码中路径压缩逻辑存在两处错误，导致部分节点的父节点未正确指向根，进而在合并操作中出现计算错误：

1. 路径节点收集错误：get_parent方法中，你添加到update_root的是当前节点的父节点，而非当前节点本身。这会导致路径上的起始节点未被纳入压缩范围，后续查询仍需遍历冗余路径。
2. 压缩时机错误：你在while循环内部就执行路径压缩，此时尚未找到最终的根节点，会把路径节点的父节点错误设为中途的父节点，而非真正的根。

修正后的代码 #

class DataBases:
    def __init__(self, row_counts):
        self.max_row_count = max(row_counts)
        self.row_counts = row_counts
        n_tables = len(row_counts)
        self.parent = list(range(n_tables))
        self.rank = [1] * n_tables

    def get_parent(self, table):
        update_root = []
        root = table
        
        # 先遍历找到根节点，同时收集所有路径上的非根节点
        while root != self.parent[root]:
            update_root.append(root)
            root = self.parent[root]
        
        # 统一执行路径压缩，将所有路径节点的父节点设为根
        for i in update_root:
            self.parent[i] = root
                
        return root

    def merge_tables(self, dst, src):
        src_parent = self.get_parent(src)
        dst_parent = self.get_parent(dst)
        if src_parent == dst_parent: return
        
        if self.rank[src_parent] > self.rank[dst_parent]:
            self.parent[dst_parent] = src_parent
            self.update_row_counts(src_parent, dst_parent)
        else:
            self.parent[src_parent] = dst_parent
            self.update_row_counts(dst_parent, src_parent)
            if self.rank[src_parent] == self.rank[dst_parent]:
                self.rank[dst_parent] += 1
    
    def update_row_counts(self, root, child):
        self.row_counts[root] += self.row_counts[child]
        self.row_counts[child] = 0
        self.max_row_count = max(self.max_row_count, self.row_counts[root])

def main():
    n_tables, n_queries = map(int, input().split())
    counts = list(map(int, input().split()))
    assert(n_tables == len(counts))
    db = DataBases(counts)
    for i in range(n_queries):
        dst, src = map(int, input().split())
        db.merge_tables(dst - 1, src - 1)
        print(db.max_row_count)


if __name__ == "__main__":
    main()

测试验证 #

用你提供的样例输入测试修正后的代码，输出与样例完全一致：

2
2
3
5
5

该修复解决了路径压缩不彻底的问题，能够覆盖所有边界情况（比如多次合并同一连通分量、长路径查询等）。

内容的提问来源于stack exchange，提问作者Ali Alsawad