POJ - 1308 Is It A Tree?（并查集）

POJ - 1308 Is It A Tree?（并查集）

题目大意：传送门

对于每一组测试样例，给出若干条无向边，判断由这些无向边构成的图是否为无环连通图

题目分析：

要点1：

无环联通图(树)的性质：边数=点数-1。统计点数和边数

要点2：

每次加边，对于这条边的两个顶点，如果这两个点属于同一个集合，那么说明如果将这条边加上的话原图就会成环，即不能构成无环连通图。否则就将这条边加上。

要点3：

此题可能存在空图，空图输出也满足条件

题目代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int p[N], st[N];
int test = 0;

void init()
{
	for (int i = 1; i <= N - 1; i++)
		p[i] = i;
	memset(st, 0, sizeof st);
}

int find(int x)
{
	if (p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}

void merge(int a, int b)
{
	if (find(a) != find(b))
		p[find(b)] = find(a);
}

int main()
{
	int a, b;
	while (cin >> a >> b)
	{
		init();

		if (a == -1 && b == -1)
			return 0;
		int point = 0, edge = 0;
		if (a == 0 && b == 0)
		{
			printf("Case %d is a tree.\n", ++test);
			continue;
		}
		bool flag = true;
		if (!st[a]) st[a] = 1, point++;
		if (!st[b]) st[b] = 1, point++;
		merge(a, b), edge++;
		while (cin >> a >> b)
		{
			if (a == 0 && b == 0)
				break;

			if (!st[a]) st[a] = 1, point++;
			if (!st[b]) st[b] = 1, point++;
			if (find(a) == find(b))
				flag = false;
			merge(a, b);
			edge++;
		}
		if (flag && edge == point - 1)
			printf("Case %d is a tree.\n", ++test);
		else
			printf("Case %d is not a tree.\n", ++test);
	}
}