POJ 1308 Is It A Tree 題解

/* POJ 1308
 * By Ceeji
 * http://poj.org/problem?id=1308
 * 
 */
 
#include <iostream>
#include <cstring>
 
using namespace std;
 
const int MAX_N = 200;
 
int father[MAX_N];
bool has_point[MAX_N];
int case_number = 0;
 
void init_set ()
{
	memset (father, 0, sizeof(father)); // 0 means that the father is itself.
	memset (has_point, 0, sizeof(has_point));
}
 
int get_father (const int i)
{
	if (father[i] == 0 || father[i] == i)
	{
		father[i] = i;
		return i;
	}
	int tmp = get_father(father[i]);
	father[i] = tmp;
	return tmp;
}
 
/* union : point x to y */
void set_union (const int x, const int y)
{
	int fx = get_father(x);
	int fy = get_father(y);
	father[fx] = fy;
}
 
int maxof (const int x, const int y)
{
	return x > y ? x : y;
}
 
int do_work ()
{
	init_set ();
	int s, t, max = 0;
	bool finish = false;
	while (cin >> s >> t)
	{
		if (s > 0 && t > 0) // if s or t is not greater than 0, it is the end descripter.
		{
			max = maxof (maxof (max, s), t);
			has_point[s] = true;
			has_point[t] = true;
			if (get_father(s) != get_father(t))
				set_union(s, t);
			else
			{
				cout << "Case " << case_number << " is not a tree." << endl;
				finish = true;
			}
		}
		else
		{
			if (s == -1 && t == -1)
			{
				return 1;
			}
			break;
		}
	}
	if (!finish)
	{
		int f = get_father(max);
		for (int i = 2; i <= max; ++i)
			if (has_point[i] && get_father(i) != f)
			{
				cout << "Case " << case_number << " is not a tree." << endl;
				finish = true;
				break;
			}
	}
	if (!finish)
		cout << "Case " << case_number << " is a tree." << endl;
	return 0;
}
 
int main()
{
	while (true)
	{
		++case_number;
		if (do_work())
			return 0;
	}
	return 0;
}