注册 登录
编程论坛 C++教室

[求助]不相交集合、数据结构。

aipb2007 发布于 2007-10-09 17:23, 642 次点击
用链表实现,只需要3个功能。

make_set(x) //建立一个只含元素x(假设整数)的集合

find_set(x) //返回x元素所在集合的代表(什么都可以,只需在不改变集合前提下多次调用返回相同结果)

union(x,y) //合并x元素和y元素所在集合成一个新的集合


链表实现。

在某个点上有点卡大家没事谢谢,我吸取下!
1 回复
#2
aipb20072007-10-09 19:52
这个也称为“并查集”,我就是想问问,怎么用链表在O(1)内实现find_set(x)???

本来这个数据结构是用树来做以获取高效率的。
1