题解 | Is It A Tree?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<algorithm>
#include<vector>
using namespace std;


//判树条件：连通、边数=顶点数-1、入度不大于1

//多组分组输入且有结束条件：
//while(1)
// {
//	if(总结束条件)
// {
//		break;
//	else if(分组结束条件)
// {
//		判断并输出结果;
//		重置初始化;
// }
//	else
// {
//		组内处理流程;
// }
//}


//并查集
int father[10001];//存各节点对应根节点
void InitDisjointSet(int n) {
	//初始化，每个节点的根节点设为自己
	for (int i = 1; i <= n; ++i) {
		father[i] = i;
	}
}
int FindDisjointSet(int u) {
	//寻找根节点
	if (u == father[u]) {
		//如果自己就是根节点直接返回
		return u;
	}
	else {
		//return FindDisjointSet(father[u]);原版，容易导致退化为链表
		//改进：每次先更新当前节点的根再返回
		father[u] = FindDisjointSet(father[u]);//递归访问上一级
		return father[u];
	}
}
void UnionDisjointSet(int u, int v) {
	//合并v所在的集合到u的根下面
	int uroot = FindDisjointSet(u);
	int vroot = FindDisjointSet(v);
	father[vroot] = uroot;
}




int main() {
	int u, v;
	InitDisjointSet(10001);
	int edgeCount = 0;
	int vertexCount = 0;
	//vector默认填充0
	vector<int>vertex(10001);//vertex[i]为0说明i未出现过
	vector<int>inDegree(10001);//记录i的入度
	bool isOK = true;
	int caseIdx = 1;
	while (1) {
		scanf("%d%d", &u, &v);
		if (u == -1 && v == -1) {
			break;
		}
		else if (u == 0 && v == 0) {
			//一个图的所有边已经记录完成了
			//边等于顶点减一
			if (vertexCount != edgeCount+1) {
				isOK = false;
			}
			//空树特例
			if (vertexCount == 0 && edgeCount == 0) {
				isOK = true;
			}
			//输出结果
			if (isOK == true) {
				printf("Case %d is a tree.\n", caseIdx);
			}
			else {
				printf("Case %d is not a tree.\n", caseIdx);
			}

			//重置代码
			InitDisjointSet(10001);
			edgeCount = 0;
			vertexCount = 0;
			for (int i = 0; i < 10001; i++) {
				vertex[i] = 0;
				inDegree[i] = 0;
			}
			isOK = true;
			caseIdx++;
		}
		else {
			//加入新边
			++edgeCount;
			if (vertex[u] == 0) {
				vertex[u] = 1;
				++vertexCount;
			}
			if (vertex[v] == 0) {
				vertex[v] = 1;
				++vertexCount;
			}
			if (FindDisjointSet(u) == FindDisjointSet(v)) {
				isOK = false;
			}
			else {
				UnionDisjointSet(u, v);
			}
			++inDegree[v];
			if (inDegree[v] >= 2) {
				isOK = false;
			}
		}
	}

	return 0;
}