1272.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include <iostream>
#include <cstdio>
using namespace std;
int set[100010];
bool hash[100010];
void makeset()
{
	int i;
	for (i = 1; i <= 100000; i++)
	{
		set[i] = i;
		hash[i] = false;
	}
}
int find(int x)
{
	int i, r = x;
	while (r != set[r])
	{
		r = set[r];
	}
	while (x != r)
	{
		i = set[x];
		set[x] = r;
		x = i;
	}
	return r;
}
void unions(int x, int y)
{
	int a = find(x);
	int b = find(y);
	if (a != b)
	{
		set[a] = b;
	}
}
int main()
{
	int a, b, i, node = 0, edge = 0, gen = 0;
	makeset();
	while (scanf("%d %d", &a, &b) == 2) 
	{
		if (a == 0 && b == 0)
		{
			getchar();
			for (i = 1; i <= 100000; i++)
			{
				if (hash[i] == true && set[i] == i)
				{
					gen++;
				}
			}
			if ((gen == 1 && edge + 1 == node) || edge == 0)
			{
				cout << "Yes" << endl;
			}
			else
			{
				cout << "No" << endl;
			}
			gen  = 0;
			edge = 0;
			node = 0;
			makeset();
		}
		else if (a == -1 && b == -1)
		{
			break;
		}
		else
		{
			node += hash[a] == false;
			node += hash[b] == false;
			hash[a] = true;
			hash[b] = true;
			edge++;
			unions(a, b);
		}
	}
	return 0;
}