HDU 1272 小希的迷宫（并查集）

HDU 1272 小希的迷宫

https://vjudge.net/problem/HDU-1272

思路：
1.不能有环 2.所有点之间都要连通
我们可以用并查集，没有环并且只有一个集合（祖先）。

Code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 5;
int f[maxn];
bool book[maxn];
bool flag;
void init()
{
	flag = true;
	for (int i = 0; i < maxn; ++i)
	{
		f[i] = i;
		book[i] = false;
	}
}
int getf(int i)
{
	if (f[i] != i)
		f[i] = getf(f[i]);
	return f[i];
}
bool mergee(int x, int y)
{
	int xx = getf(x);
	int yy = getf(y);
	if (xx == yy)
		return false;
	f[yy] = xx;
	return true;
}
int main()
{
	int x, y;
	while (scanf("%d%d", &x, &y) != EOF)
	{
		if (x == 0 && y == 0)
		{
			printf("Yes\n");
			continue;
		}
		if (x == -1 && y == -1)
			break;
		init();
		mergee(x, y);
		book[x] = book[y] = true;
		while (scanf("%d%d", &x, &y) != EOF)
		{
			if (x == 0 && y == 0)
				break;
			book[x] = book[y] = true;
			if (!mergee(x, y))
				flag = false;
		}
		if (!flag)
		{
			printf("No\n");
			continue;
		}
		int sum = 0;
		for (int i = 0; i < maxn; i++)
			if (book[i] && f[i] == i)
				sum++;
		if (sum == 1)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}