c++并查集优化（基于size和rank）

2023-08-01 15:18:04 75

#ifndefUNION_FIND3_H_ #defineUNION_FIND3_H_ #include #include namespaceUF3 { classUnionFind { private: int*parent; int*sz;//sz[i]就表示以i为根的集合中元素的个数 intcount; public: UnionFind(intcount) { this->count=count; parent=newint[count]; sz=newint[count]; for(inti=0;i=0); while(p!=parent[p])//这个是写到find里面的 { p=parent[p]; } returnp; } voidunionElements(intp,intq) { intpRoot=find(p); intqRoot=find(q); if(pRoot==qRoot) return; if(sz[pRoot]

基于rank的代码：UnionFind4.h

#ifndefUNION_FIND4_H_
#defineUNION_FIND4_H_

#include
#include

namespaceUF4
{
	classUnionFind
	{
	private:
		int*parent;
		int*rank;//rank[i]就表示以i为根的集合的层数
		intcount;

	public:
		UnionFind(intcount)
		{
			this->count=count;
			parent=newint[count];
			rank=newint[count];
			for(inti=0;i=0);
			while(p!=parent[p])//这个是写到find里面的
			{
				p=parent[p];
			}

			returnp;
		}

		voidunionElements(intp,intq)
		{

			intpRoot=find(p);
			intqRoot=find(q);

			if(pRoot==qRoot)
				return;
			if(rank[pRoot]rank[qRoot])
			{
				parent[qRoot]=pRoot;
			}
			else
			{
				parent[pRoot]=qRoot;//这里谁指向谁无所谓
				rank[qRoot]++;
			}

		}

		boolisConnected(intp,intq)
		{
			returnfind(p)==find(q);
		}


	};
};


#endif

剩下的头文件和main文件在上一个并查集的博客中有，就不再粘贴出来了

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

c++并查集优化（基于size和rank）

热门推荐

随机推荐