WeightedQuickUnionUF[动态连通性问题] -- C++ 实现


实现代码

// WeightedQuickUnionUF.h
#ifndef WEIGHTEDQUICKUNION_H
#define WEIGHTEDQUICKUNION_H

namespace jay{
	class WeightedQuickUnionUF
	{
	public:
		WeightedQuickUnionUF(int nMaxNumber);
		WeightedQuickUnionUF(const WeightedQuickUnionUF& rhs);
		WeightedQuickUnionUF& operator=(WeightedQuickUnionUF& rhs);
		~WeightedQuickUnionUF();

		void Union(int p,int q);
		bool isConnected(int p,int q);
		int GetCount();
		int Find(int p);
		void CheckValue(int p);
	private:
		// 连通分量的个数
		int m_nCount;
		// 每个分量的起点分量[parrent]
		int *m_id;
		// 对应分量连接的数量
		int *m_id_size;
		//最大数
		int m_nMaxNumber;
	};

};

#endif
// WeightedQuickUnionUF.cpp
#include<iostream>
#include "WeightedQuickUnionUF.h"

using namespace jay;

WeightedQuickUnionUF::WeightedQuickUnionUF(int nMaxNumber)
{
	m_nMaxNumber = nMaxNumber;
	m_id = new int[nMaxNumber];
	if (m_id == NULL)
	{
		throw "Failed to allocate memory!";
	}

	m_id_size = new int[nMaxNumber];
	if (m_id_size == NULL)
	{
		throw "Failed to allocate memory!";
	}

	m_nCount = nMaxNumber;
	for (int i=0;i<nMaxNumber;i++)
	{
		m_id[i] = i;
		m_id_size[i] = 1;
	}
}

WeightedQuickUnionUF::~WeightedQuickUnionUF()
{
	delete []m_id;
	delete []m_id_size;
}

int WeightedQuickUnionUF::GetCount() 
{
	return m_nCount;
}

void WeightedQuickUnionUF::CheckValue(int p)
{
	if (p <0 || p> m_nMaxNumber)
	{
		throw "p is a valid index!";
	}
}

int WeightedQuickUnionUF::Find(int p) 
{
	CheckValue(p);

	while (p != m_id[p])
	{
		p = m_id[p];
	}

	return p;
}

bool WeightedQuickUnionUF::isConnected(int p,int q)
{
	CheckValue(p);
	CheckValue(q);
	return Find(p) == Find(q);
}

void WeightedQuickUnionUF::Union(int p,int q)
{
	int pID = Find(p);
	int qID = Find(q);

	if (pID == qID) 
		return;

	// 元素少的连通分量合拼到元素多的分量
	if (m_id_size[pID] < m_id_size[qID])
	{
		m_id[pID] = qID;
		m_id_size[qID] += m_id_size[pID];
	} 
	else
	{
		m_id[qID] = pID;
		m_id_size[pID] += m_id_size[qID];
	}

	m_nCount--;

}



测试代码

//main.cpp
#include "WeightedQuickUnionUF.h"
#include <time.h>
#include <iostream>
#include<windows.h>
using namespace std;
using namespace jay;

class TimeCalculator
{
public: 
	TimeCalculator()
	{
		m_dtimebegin = clock();
	}

	void PrintTimeInfo()
	{
		double dstop,ddurationTime;
		dstop = clock();
		ddurationTime = ((dstop-m_dtimebegin));

		cout << "操作耗时:" << ddurationTime << " ms" << endl;
	}

	void RestartBegin()
	{
		m_dtimebegin = clock();
	}

private:
	double m_dtimebegin;
};

int main(int argc, char* argv[])
{
	TimeCalculator timec;

	int nMaxNun(0);
	cin>>nMaxNun;
	WeightedQuickUnionUF testQF(nMaxNun);

	int p;
	int q;
	while(cin>>p)
	{
		
		cin>>q;
		
		if (testQF.isConnected(p,q))
			continue;

		testQF.Union(p,q);

 	//	cout <<p <<" "<<q <<endl;

	}
	timec.PrintTimeInfo();
	cout<< "当前连通分量有 " << testQF.GetCount() << " 个"<<endl;
	cout<< "1,2 connected? " << testQF.isConnected(1,2)<<endl;
	cout<< "1,4 connected? " << testQF.isConnected(1,4)<<endl;
	cout<< "6,2 connected? " << testQF.isConnected(6,2)<<endl;
	cout<< "6,7 connected? " << testQF.isConnected(6,7)<<endl;
	cout<< "9,4 connected? " << testQF.isConnected(9,4)<<endl;
	cout<< "9,3 connected? " << testQF.isConnected(9,3)<<endl;
	cout<< "1,6 connected? " << testQF.isConnected(1,6)<<endl;
	cout<< "1,9 connected? " << testQF.isConnected(1,9)<<endl;

	// 打印操作耗时
	timec.PrintTimeInfo();

}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。