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


实现代码

// QuickUnionUF.h
#ifndef QUICKUNIONUF_H
#define QUICKUNIONUF_H

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

		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;
		// 每个分量的起点分量
		int *m_id;
		//最大数
		int m_nMaxNumber;
	};

};

#endif
// QuickFindUF.cpp
#include<iostream>
#include "QuickUnionUF.h"

using namespace jay;

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


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

QuickUnionUF::~QuickUnionUF()
{
	delete []m_id;
}

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

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

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

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

	return p;

}

bool QuickUnionUF::isConnected(int p,int q)
{
	CheckValue(p);
	CheckValue(q);
	return m_id[p] == m_id[q];
}

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

	if (pID == qID) 
		return;

	m_id[pID] = qID;

	m_nCount--;

}



测试代码

//main.cpp
#include "QuickUnionUF.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 = ((double)(dstop-m_dtimebegin));

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

private:
	double m_dtimebegin;
};

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

	int nMaxNun(0);
	cin>>nMaxNun;
	QuickUnionUF 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;
	}

	cout<< "当前连通分量有 " << testQF.GetCount() << " 个"<<endl;
	cout<< "1,2 connected? " << testQF.isConnected(1,2)<<endl;
	cout<< "1,4 connected? " << testQF.isConnected(1,4)<<endl;

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

}

 

暂无评论

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