【笔试集锦】并查集 && 大数打印

题目一

已知有n个人和m对好友关系存储于r中，如果两个人是直接或间接的好友，则认为他们属于同一个朋友圈，编程求出这n个人里一共有多少个朋友圈？

比如：n=5，m=3，r={{1，2}，{2，3}，{4，5}}，则认为1、2属于一个朋友圈，2、3是一个朋友圈，4、5是一个朋友圈，则1、2、3属于同一个朋友圈，4、5属于另一个朋友圈，共有两个朋友圈。

• 并查集的实现过程

并查集是一种树形数据结构，用于处理一些不相交集合的合并及查询，常以森林来表示。

集是让多个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。

下面我们使用上述例子加以说明合并过程：

① 编号。底层数据结构采用vector开辟大小为6的空间，并将每个值初始化为-1，表示元素是一个单独的集合（多开辟下标为0的空间是为了方便计算）。

② 合并。将{1，2}合并成一个集合，将下标为2的值加到下标为1处，再更新下标为2的值，即根节点为1。

③ 与②同理，{2，3}合并时，先找到两者的根节点，剩下操作与②一致。但是要注意的是：如果直接让2作为3的根，势必会增加森林的高度，不利于搜索，因此，我们让1作为2、3的根。

④ 同理，让{4，5}进行并集操作，得到两个不同的集合。

源代码及注释

#include <iostream>
#include <vector>
using namespace std;
class UnionSet
{
public:
	UnionSet(int size)
	{
		//开辟一个大小为size的数组，并初始化为-1
		_us.resize(size, -1);
	}
	//获取并查集的根
	int _FindRoot(int index)
	{
		int _root = index;
		//小于0为根，大于等于0为子节点
		while (_us[_root] >= 0)
		{
			_root = _us[_root];
		}
		return _root;
	}
	//合并并查集
	void _Union(int x, int y)
	{
		//得到两个并查集的根
		int _root1 = _FindRoot(x);
		int _root2 = _FindRoot(y);
		//保证两个结点处于不同集合时才合并
		if (_root1 != _root2)
		{
			_us[_root1] += _us[_root2];//更新有效元素个数
			_us[_root2] = _root1;//更新元素的根节点
		}
	}
	//获取集合的个数
	size_t _Count()const
	{
		size_t count = 0;
		for (int idx = 0; idx < _us.size(); ++idx)
		{
			//小于0为根节点
			if (_us[idx] < 0)
				count++;
		}
		return count - 1;//-1与是否使用下标为0有关
	}
	//查找两个元素是否属于同一个集合
	bool IsSameSet(int x, int y)
	{
		return _FindRoot(x) == _FindRoot(y);
	}
private:
	vector<int> _us;//用vector代替数组
};
int main()
{
	UnionSet us(6);
	us._Union(1, 2);
	us._Union(2, 3);
	us._Union(4, 5);
	cout << us._Count() << endl;
	if (us.IsSameSet(1, 3))
		cout << "属于同一组" << endl;
	else
		cout << "不属于同一组" << endl;
	if (us.IsSameSet(1, 5))
		cout << "属于同一组" << endl;
	else
		cout << "不属于同一组" << endl;
	system("pause");
	return 0;
}

并查集还是很妙的，其中的相关资料：http://www.cnblogs.com/horizonice/p/3658176.html

题目二

这道题属于一个经典的＂大数问题＂，一个表面看似简单的算法，却深藏很多bug。只有考虑周全，才能斩获 ，我们对递归与非递归两个版本进行分析。

• 算法要求

输入数字n，按顺序打印出从1到最大的n位10进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。

• 字符串上模拟加法

我们可以使用字符串来表示数字，每个字符都时'0'到'9'之间的某一个字符，我们需要使用一个长度位n+1的字符串（最后一位存储’\0’）。

"得到辅助空间后，我们需要做两件事":

1.在字符串表达的数字上模拟加法
2.打印字符串中的数字

① 首先我们将字符串中的每一个数字都初始化为'0'，然后从最低位递增，当最低位等于10时产生进位，并将最低位清零，直到最高位产生进位时，终止循环（借助标志位）。

② 由于我们初始化符串时给的’0’，因此，当我们打印的数字不足n位时，高位会自动补0。因此我们需要从第一个非0字符之后开始打印（可使用标志位）。

//提前声明
bool Increment(char* arr, int size);
void PrintNumber(char* arr, int size);
void Print1ToMax(int n)
{
	if (n <= 0)
		return;
	char* arr = new char[n + 1];
	memset(arr, '0', n);//初始化
	arr[n] = '\0';
	while (!Increment(arr, n))
	{
		PrintNumber(arr, n);
	}
	delete[] arr;
}
//递增
bool Increment(char* arr, int size)
{
	bool isOverflow = false;//最高位进位标志位
	int TakeOver = 0;//进位标志位
	for (int idx = size - 1; idx >= 0 ; --idx)
	{
		int nSum = arr[idx] - '0' + TakeOver;
		//最低位递增
		if (idx == size - 1)
			nSum++;
		//如果nSum>=10，可能会产生进位
		if (nSum >= 10)
		{
			//最高位不进位
			if (idx == 0)
				isOverflow = true;
			//不是最高位，则进位
			else
			{
				nSum -= 10;
				TakeOver = 1;//进位标志位置1
				arr[idx] = nSum + '0';
			}
		}
		//未产生进位，直接存取
		else
		{
			arr[idx] = nSum + '0';
			break;
		}
	}
	return isOverflow;
}
//打印
void PrintNumber(char* arr, int size)
{
	bool flag = true;
	for (int idx = 0; idx < size; ++idx)
	{
		//标志位为true且字符不等于0时将标志位置为false
		if (flag && arr[idx] != '0')
			flag = false;
		//第一个不为'0'的字符(说明上一个if肯定执行了)
		if (!flag)
			cout << arr[idx] << " ";
	}
}

• 数字全排列(递归)

如果我们在数字前面补0的话，就会发现n位所有10进制数就是n个0到9的全排列，到后面打印的时候不打印0就好了。

我们采用递归可以将一个大问题划分成多个子问题来求解，我们从数字的最高位递归，直到设置了最低位，进行打印。

//提前声明
void PrintNumber(char* arr, int size);
void _Print1ToMax(char* arr, int size, int index);
void Print1ToMax(int n)
{
	if (n <= 0)
		return;
	char* arr = new char[n + 1];
	arr[n] = '\0';
	//将一个大问题划分成多个子问题
	for (int idx = 0; idx < 10; ++idx)
	{
		arr[0] = idx + '0';//将最高位分为0-9个小部分
		_Print1ToMax(arr, n, 0);
	}
}
void _Print1ToMax(char* arr, int size, int index)
{
	//最低位时，进行打印
	if (index == size - 1)
	{
		PrintNumber(arr, size);
		return;
	}
	//对0-9之间的数字进行全排列
	for (int i = 0; i < 10; ++i)
	{
		arr[index + 1] = i + '0';
		_Print1ToMax(arr, size, index + 1);//一直递归到最低位
	}
}
void PrintNumber(char* arr, int size)
{
	bool flag = true;
	for (int idx = 0; idx < size; ++idx)
	{
		//标志位为true且字符不等于0时将标志位置为false
		if (flag && arr[idx] != '0')
			flag = false;
		//第一个不为'0'的字符(说明上一个if肯定执行了)
		if (!flag)
			cout << arr[idx] << " ";
	}
	cout << "\t";
}