随笔 - 62  文章 - 96  trackbacks - 0
<2006年8月>
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

  • 积分 - 231225
  • 排名 - 106

最新评论

阅读排行榜

评论排行榜

参考文章:
http://www.cppblog.com/qywyh/archive/2006/08/16/11301.html
http://www.programfan.com/blog/article.asp?id=16879

#ifndef UFSET_H
#define UFSET_H
class UFset
{
	public:
		UFset(int);
		void Union(int ,int);
		int Find(int);
		int & operator [] (int i){return parent[i];}
		int size(){return length;}
	private:
		int length;//集合的个数
		int * parent;
};
UFset::UFset(int len)
{
	length = len;
	parent = new int [length + 1];
	for(int k = 1; k <= length; k++)
		parent[k] = -1;
}
int UFset::Find(int x)
{
	 int i;
	 for(i = x; parent[i] >= 0; i = parent[i]);//搜索根节点
	 while(i!=x)//路径压缩
	 {
		  int tmp = parent[x];
		  parent[x] = i;
		  x = tmp;
	 }
	 return i;
}
void UFset::Union(int x,int y)//合并
{
	int pX = Find(x);
	int pY = Find(y);
	if(pX != pY)
	{
		int tmp = parent[pX] + parent[pY];
		if(parent[pX] > parent[pY])
		{
			parent[pX] = pY;
			parent[pY] = tmp;
		}
		else 
		{
			parent[pY] = pX;
			parent[pX] = tmp;
		}
		length--;
	}
}
#endif
posted on 2006-08-30 00:27 beyonlin 阅读(445) 评论(0)  编辑 收藏 引用 所属分类: acm之路

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理