ACM程序设计
杭州电子科技大学刘春英
******@hdu.
11月14号,
学校有!
ACM
比赛
每周一星(5):
王振峰
第六讲
并查集 (Disjoint Set)
导引问题
在某个城市里住着n个人,现在给定关于 n个人的m条信息(即某2个人认识),
假设所有认识的人一定属于同一个单位,请计算该城市最多有多少单位?
如何实现?
什么是并查集?
英文:Disjoint Set,即“不相交集合”
将编号分别为1…N的N个对象划分为不相交集合,
在每个集合中,选择其中某个元素代表所在集合。
常见两种操作:
合并两个集合
查找某元素属于哪个集合
所以,也称为“并查集”
实现方法(1)
用编号最小的元素标记所在集合;
定义一个数组 set[1..n] ,其中set[i] 表示元素i 所在的集合;
i
Set(i)
不相交集合: {1,3,7}, {4}, {2,5,9,10}, {6,8}
方法(1)——效率分析
find1(x)
{
return set[x];
}
Merge1(a,b)
{ i = min(a,b);
j = max(a,b);
for (k=1; k<=N; k++) {
if (set[k] == j)
set[k] = i;
}
}
Θ(1)
Θ(N)
有待改进?
对于“合并操作”,必须搜索全部元素!
树结构如何?
（HDUACM2010版06）并查集（最小生成树） 来自淘豆网m.daumloan.com转载请标明出处.
