题解 | Is It A Tree?

#include<iostream>
#include<cstring>
using namespace std;
const int N = 10010;
int p[N];
int id[N];//保存结点入度
int node_num, e_num;//记录结点数量以及边的数量
bool visit[N];//表明结点是否被访问过
bool not_true = false;
int find(int x) {
	//返回祖宗结点顺便加上路径压缩
	if (p[x] != x)p[x] = find(p[x]);
	return p[x];
}
void init() {
	for (int i = 0; i < 10010; i++) {
		p[i] = i;
	}
}
void Union(int x, int y) {
	//合并操作
	if (find(x) != find(y))p[find(x)] = find(y);//修改根结点的指向就是合并操作
}
int main() {
	//本题要积累起的知识点
	// 1.如何判断图是否是一颗树，每个结点的入度最大为1
	// 2.其次不能有环--得用并查集来判断是否有环
	//       判断是否有环的思路：若一个图已经联通的情况下，再不增加结点的情况下增加一条边就会形成环
	// 3.在以上两条条件都满足的情况下，得确保整个图是联通的，也就是要顶点数等于边的数量加1
	int x, y;
	int t = 0;//表明当前是第几个案例
	//并查集别忘了要先初始化
	init();

	//读入多组数据的题就是要注意在下一组数据开始前恢复原来的状态
	while (cin >> x >> y) {
		if (x == 0 && y == 0) {
			//先判断该情况是否是一个树
			t++;
			//注意空树也是个树，这种情况要特判
			if (node_num == 0 && e_num == 0) {
				printf("Case %d is a tree.\n", t);
				continue;
			}
			//刚刚没有.纠错了，这点要注意
			if (node_num == e_num + 1 && not_true == false)printf("Case %d is a tree.\n", t);
			else printf("Case %d is not a tree.\n", t);

			//插入结束清空恢复数据
			memset(visit, 0, sizeof visit);
			memset(id, 0, sizeof id);
			init();
			not_true = false;
			node_num = 0, e_num = 0;
			//此时0，0就不要再执行接下来从操作了
			continue;
		}
		if (x == -1 & y == -1)break;
		//这个要在插入边前判断
		if (find(x) == find(y)) {
			//如果这两个结点所在部分有相同的根结点，说明已经联通了
			//这时候再加入一条边肯定就会成环，不会形成树
			not_true = true;
		}
		Union(x, y);
		//别忘了还要计算入度
		if (id[y] == 0)id[y]++;
		else not_true = true;
		
		e_num++;
		if (!visit[x])visit[x]=true,node_num++;
		if (!visit[y])visit[y]=true,node_num++;
		
	}
	return 0;
}