POJ 1308 Is It A Tree 题解

这道题是一道并查集的题目。和普通并查集相比,主要有几点需要注意:

  1. 注意空树的处理。
  2. 如果在合并的时候,这两个点已经在树中,说明路径重复,不是合法的树。
/* 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;
}

题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名

当前页阅读量为: