前言并查集(disjoint set union, DSU)维护一组不相交的集合,支持两个操作:查询某个元素属于哪个集合(find),以及把两个集合合并(unite)。教科书实现通常用数组:parent[i]指向父节点,根节点指向自己,配合路径压缩与按秩合并,单次操作的均摊复杂度是 O(α(n)),其中 α 是反阿克曼函数,增长极慢,实际可视为常数。数组版的前提是「元素可以用 0 到 n-1 的整数编号」。现实中的数据常常不是这样:元素是用户名、商品编号、IP 地址、或者一个含多个字段的结构体。这时有两种做法:先做一次离散化,把每个键映射到连续整数;或者直接用关联容器存键 - 父键。后者就是所谓「用 map 实现并查集」。map 版并查集的代码更短,不需要预先收集全部元素,支持动态插入,键可以是任意可比较类型。代价是每次找父节点都要在 map 里查一次,单次操作从「近似常数」变成「带一个对数因子」。在元素数量不大、或者键本身不是整数时,这个代价完全可以接受;在百万级整数、且操作频繁的场景,数组版仍然更快。最常见的误解是在find里写parent_[x],以为只是读取。std::map::operator[]在键不存在时会插入一个默认构造的值,于是一次查询就悄悄造出一个「父节点是自己」的新集合,groupCount()随之变大,而且这个新键可能被后续逻辑当成真实元素。正确做法是用find或at,并在键不存在时明确报错。第二个误解是以为用了 map 就自动获得了路径压缩。路径压缩是算法层面的动作,与容器无关:必须显式地把路径上每个节点的父指针改到根,否则树会退化成链,单次查询变成 O(n)。第三个误解是忽略std::map对键的要求:它需要严格弱序(strict weak ordering),默认用operator。自定义结构体如果没有定义,编译就通不过;定义了但比较不满足严格弱序,查找行为未定义。本文给出一个模板化的 map 版并查集,包含路径压缩、按集合大小合并、成员分组,并对照std::map与std::unordered_map的取舍。示例以 C17 为基准。一、结构设计核心容器是std::mapKey, Key parent_,把每个键映射到它的父键;根节点的父键是它自己。这样可以判断根:parent_[x] x(仅当 x 已存在)。为了按大小合并,再维护std::mapKey, std::size_t size_,只对根节点有意义,记录该集合的元素个数。add(key)负责登记新元素:在parent_中插入key - key,在size_中插入key - 1。用emplace的返回值判断是否真的插入,重复添加返回false。find(key)先沿父链走到根,再把路径上所有节点直接挂到根上。若键不存在,抛std::out_of_range,而不是静默插入。unite(a, b)分别找到两个根;相同则返回false;否则把较小的集合挂到较大的根下,更新大小,并从size_中删除失去根身份的键。groupCount()直接返回size_.size(),因为每个集合恰好有一个根在size_中。二、路径压缩的实现路径压缩有两种常见写法。第一种是「隔代压缩」:parent_[x] parent_[parent_[x]],每次只把节点往上提一层,循环执行也能逐步降低树高,但单次find不一定把路径压平。第二种是「完全压缩」:先走到根,再沿原路径把每个节点的父指针改成根。本文采用第二种,查询后树高变为 1。实现时要注意:压缩阶段不能再用operator[],因为路径上的键都已在 map 中,用find拿到迭代器后直接改second即可。修改std::map中已存在元素的映射值不会使任何迭代器失效,这一点与std::vector不同,是安全的前提。三、按大小合并只做路径压缩、不做按大小合并,复杂度仍然可以接受,但最坏情况下的树高缺少保证。按大小合并保证每次把较小的树接到较大的树下,树高不超过 O(log n);再叠加路径压缩,均摊代价更低。合并时先比较两个根在size_中的值,若前者小则交换根,然后把parent_[rb] ra,把大小累加到ra,最后size_.erase(rb)。删除rb很关键:如果忘了删,groupCount()会把已经不是根的键也算进去,结果偏大。四、完整示例下面的示例实现模板类MapDsu,以字符串为键,演示添加、合并、查询、成员分组。// 适用于 C17#include cstddef#include iostream#include map#include stdexcept#include string#include utility#include vectortemplate typename Keyclass MapDsu {public:bool add(const Key key) {const auto inserted parent_.emplace(key, key);if (inserted.second) {size_.emplace(key, std::size_t{1});}return inserted.second;}bool contains(const Key key) const {return parent_.find(key) ! parent_.end();}// 返回根;键不存在时抛异常,绝不隐式插入Key find(const Key key) {auto it parent_.find(key);if (it parent_.end()) {throw std::out_of_range(MapDsu::find: unknown key);}Key root key;auto rootIt parent_.find(root);while (rootIt-second ! rootIt-first) {root rootIt-second;rootIt parent_.find(root);}// 完全路径压缩:把路径上每个节点直接挂到根Key cur key;while (cur ! root) {auto curIt parent_.find(cur);const Key next curIt-second;curIt-second root;cur next;}return root;}bool same(const Key a, const Key b) {return find(a) find(b);}bool unite(const Key a, const Key b) {Key ra find(a);Key rb find(b);if (ra rb) {return false;}if (size_.at(ra) size_.at(rb)) {std::swap(ra, rb);}parent_.at(rb) ra;size_.at(ra) size_.at(rb);size_.erase(rb); // 旧根不再计数return true;}std::size_t groupCount() const {return size_.size();}std::size_t groupSize(const Key key) {return size_.at(find(key));}// 把每个集合的成员收集到 map根, 成员列表std::mapKey, std::vectorKey groups() {std::mapKey, std::vectorKey result;for (const auto kv : parent_) {result[find(kv.first)].push_back(kv.first);}return result;}private:std::mapKey, Key parent_;std::mapKey, std::size_t size_;};int main() {MapDsustd::string dsu;for (const char* name : {alice, bob, carol, dave, erin}) {dsu.add(name);}dsu.unite(alice, bob);dsu.unite(bob, carol);dsu.unite(dave, erin);dsu.unite(carol, alice); // 已同组,返回 falsestd::cout groups dsu.groupCount() \n;std::cout alice group size dsu.groupSize(alice) \n;std::cout dave group size dsu.groupSize(dave) \n;std::cout same(alice,carol) (dsu.same(alice, carol) ? true : false) \n;std::cout same(alice,dave) (dsu.same(alice, dave) ? true : false) \n;for (const auto group : dsu.groups()) {std::cout group.first :;for (const std::string member : group.second) {std::cout member;}std::cout \n;}return 0;}按标准语义推演:五个键各成一组;合并 alice 与 bob、bob 与 carol 后,三者在同一组;dave 与 erin 合并为另一组;第四次合并的两个根相同,返回false。因此groups 2,alice组大小为 3,dave组大小为 2,same(alice,carol)为真,same(alice,dave)为假。按「相等大小不交换」的写法,第一组的根是alice,第二组的根是dave,分组输出为alice: alice bob carol与dave: dave erin。以上只按代码逻辑推导,未经编译运行核对。五、map 与 unordered_map 的取舍std::map基于红黑树,查找、插入、删除都是 O(log n),迭代器稳定:插入不会使已有迭代器失效,删除只影响被删元素。键按operator有序,分组输出天然按字典序。std::unordered_map基于哈希表,查找均摊 O(1),最坏 O(n)(大量哈希冲突时)。插入可能触发 rehash,使迭代器失效,但指向元素的引用与指针仍有效。键需要std::hash特化与operator。对并查集来说,操作的主体是「多次按键找父节点」,unordered_map的均摊常数通常更快;但若键类型没有现成的哈希、或需要按顺序输出分组,map更省事。选择时先看键类型,再看是否需要有序遍历,不要只看复杂度记号。维度std::mapstd::unordered_map底层结构红黑树哈希表单次查找O(log n)均摊 O(1),最坏 O(n)键的要求operator严格弱序std::hashoperator有序遍历支持不支持插入对迭代器不失效可能 rehash 失效单次find总代价O(log n·α(n))均摊 O(α(n))适用场景键有序、无哈希键可哈希、追求速度常见坑点一、在find中用operator[]读取父节点❌while (parent_[x] ! x) x parent_[x];键不存在时会插入一个默认构造的键,凭空多出一个集合。✅ 用parent_.find(x)或parent_.at(x);键不存在时抛异常或返回失败标记。二、路径压缩只做一层且只做一次❌parent_[x] parent_[parent_[x]];只把起点上提一层,长链依旧存在。✅ 先走到根,再沿路径把每个节点挂到根;或用循环反复执行隔代压缩直到稳定。三、合并后忘记删除旧根的大小记录❌ 只写parent_[rb] ra; size_[ra] size_[rb];,groupCount()把rb也算一个组。✅ 合并后size_.erase(rb),让size_中只保留根。四、认为 map 版并查集仍是 O(α(n))❌ 把数组版的复杂度结论直接套过来,忽略每次找父节点都要在 map 中查找。✅ 单次操作是 O(log n·α(n))(map)或均摊 O(α(n))(unordered_map);元素规模大时优先数组版。五、对不存在的键调用unite❌ 两个键中有一个没add,直接合并时抛std::out_of_range,调用方没有准备。✅ 明确策略:要么入口统一add,要么提供addIfMissing并在文档中说明。六、自定义键没有定义严格弱序❌ 结构体只定义了operator,直接作为std::map的键,编译失败;或只比较部分字段,导致等价键被当成不同键。✅ 定义满足严格弱序的operator(C20 可用),并保证「互不小于」与「相等」一致。七、在groups()遍历中隐式插入❌ 分组循环里调用会插入新键的operator[],使parent_的迭代器失效或改变遍历范围。✅ 分组只调用不插入的find;修改已存在元素的映射值不会使std::map迭代器失效。八、混淆「同组」与「直接父子」❌ 用parent_[a] b判断 a 与 b 是否同组,路径压缩后父指针可能直接指向根。✅ 用find(a) find(b)比较根;父指针只表示树结构,不表示集合关系。总结map 版并查集把数组版的parent[i]换成parent[key],算法完全不变,变的是每次访问的代价与键的类型约束。三个操作对应三件事:add登记,find走到根并压平路径,unite按大小合并并维护根集合。实现时守住四条:find只用find/at,不隐式插入;路径压缩要压整条路径;合并后删除旧根的大小记录;自定义键必须满足严格弱序。做到这四点,map 版并查集就能在键不是整数、元素动态增加的场景里稳定工作。操作作用关键点add(key)登记新元素重复添加返回falsefind(key)返回根键不存在抛异常,路径完全压缩unite(a,b)合并两组按大小合并,删除旧根记录same(a,b)是否同组比较根,不比较父指针groupCount()组数等于size_的元素个数groups()成员分组遍历全部键,按根归并