7.1 不相交集（并查集）

文档摘要

7.1 不相交集（并查集） 7.1 不相交集（并查集）不相交集（Disjoint Set），又称并查集（Union-Find Set），是一种用于管理分组的数据结构。它维护着一些互不相交的集合，并提供两种主要操作： Find(x): 确定元素 x 属于哪个集合。该操作返回 x 所在集合的代表元素。 Union(x, y): 将包含元素 x 的集合和包含元素 y 的集合合并成一个集合。并查集在解决某些问题时非常高效，例如判断图的连通性、求最小生成树（Kruskal算法）等。 7.1.1 基本概念集合 (Set): 一组元素的集合。不相交 (Disjoint): 两个集合没有共同的元素。代表元素 (Representative): 每个集合都有一个特定的元素作为该集合的代表。