这里提到一点是”小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）“，这可以通过判断输入的二点是否在同一集合中实现，如果输入二点在同一集合中，说明有回路，也就不满足条件。第二是判断所有点是否在同一集合中，这可以通过并查集简单实现。

//2193981	2010-03-16 19:33:38	Accepted	1272	31MS	1152K	1749 B	C++
#include <iostream>
using namespace std;

const int N = 100002;

typedef struct
{
	int parent;//记录前驱
	int height;//记录集合树高度
}Node;

bool Visited[N];
Node UFSet[N];

void init()
{
	for(int i = 0; i < N; i++)
	{
		UFSet[i].parent = i;
		UFSet[i].height = 1;
		Visited[i] = false;
	}
}

int find(int x)
{//查操作，时间复杂度为O(N)
	while(x != UFSet[x].parent)
		x = UFSet[x].parent;
	return x;
}

void merge(int x, int y)
{//并操作，时间复杂度为O(1)
	x = find(x);
	y = find(y);

	//要求：x和y互不相交，否则不执行操作；若x，y在同一集合，则说明有回路
	if(x == y)
		return ;

	if(UFSet[x].height == UFSet[y].height)
	{
		UFSet[y].parent = x;
		UFSet[x].height++;
	}else if(UFSet[x].height < UFSet[y].height)
	{
		UFSet[x].parent = y;
	}else
	{
		UFSet[y].parent = x;
	}
}

int main()
{
	int a, b;
	int minc, maxc, kk, i;
	bool flag;
	while(scanf("%d %d", &a, &b) != EOF)
	{
		if(a == -1 && b == -1)
			break;
		init();
		flag = true;
		minc = N; maxc = -1;
		while(1)
		{
			if(a== 0 && b == 0)
				break;
			if(!flag)
				goto fend;
			Visited[a] = Visited[b] = true;
			if(a < minc) minc = a;
			if(b < minc) minc = b;
			if(a > maxc) maxc = a;
			if(b > maxc) maxc = b;
			a = find(a);
			b = find(b);
			if(a == b)
			{//存在回路，不符合条件
				flag = false;
				goto fend;
			}
			else
				merge(a, b);


			fend: scanf("%d %d", &a, &b);
		}
		if(flag == false)
			cout<<"No"<<endl;
		else
		{//判断图是否连通
			kk = find(minc);
			for(i = minc + 1; i <= maxc; i++)
				if(Visited[i] && find(i) != kk)
				{
					flag = false;
					break;
				}
			if(flag)
				cout<<"Yes"<<endl;
			else
				cout<<"No"<<endl;
		}

	}
	return 0;
}

• 相关文章
• 全局相关文章