题解 | 这是一棵树吗？

题目链接

思路：依次把输入结点-结点加入集合中（形成1棵树），判断是否标记false：（注意是仅标记，非立即终止树的构造）

1.有环不行：用并查集判断，在已连通的2顶点（处于同一集合，根一样），加入一条边则成环

2.多个入边不行：用一个数组记录各个顶点入度

3.不相连不行：无环的连通性：边数=结点个数-1

ps：呜呜呜呜呜呜我以后一定认真写if-else，搞了半天没accepted，逻辑检查了几遍发现是main里面第二个if后面没写else，导致本来else中的代码也默认执行了！

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int father[10001];
//初始化
void Initfun(int n) {
	for (int i = 0; i < n; i++) {
		father[i] = i;
	}
	return;
}
//找根结点
int FindFather(int i) {
	if (i == father[i]) {//根节点
		return i;
	}
	else {
		father[i] = FindFather(father[i]);
		return father[i];
	}
}
//合并并查集
void UniteSet(int a, int b) {
	if (FindFather(a) == FindFather(b)) {
		return;
	}
	else {
		father[b] = a;
	}
	return;
}

int main() {
	int node = 0;
	int edge = 0;
	int visit[10001];
	int indegree[10001];
	memset(visit, 0, sizeof(visit));
	memset(indegree, 0, sizeof(indegree));
	int a, b;
	int Case = 0;
	Initfun(10001);
	bool isOK = true;
	while (1) {
		scanf("%d%d", &a, &b);
		if (a == -1 && b == -1)break;//全部结束
		if (a == 0 && b == 0) {//一组结束
			Case++;
			//无环的连通性：边数=结点个数-1
			if (edge != node - 1) {
				isOK = false;
			}
			//特殊：空结点 
			if (edge == 0 && node == 0) {
				isOK = true;
			}
			//打印输出
			if (isOK) {
				printf("Case %d is a tree\n", Case);
			}
			else {
				printf("Case %d is not a tree\n", Case);
			}
			//重置数据，为下一组
			Initfun(10001);
			isOK = true;
			edge = 0;
			node = 0;
			memset(visit, 0, sizeof(visit));
			memset(indegree, 0, sizeof(indegree));
		}
		else {//注意else必须写上
			//建树
			edge++;
			if (visit[a] == 0) {
				node++;
				visit[a] = 1;//标记已访问
			}
			if (visit[b] == 0) {
				node++;
				visit[b] = 1;
			}
			//有环：在已连通的2顶点，加入一条边则成环
			if (FindFather(a) == FindFather(b)) {
				isOK = false;//仅标记错误，程序继续执行，但没必要合并
			}
			else {
				UniteSet(a, b);
			}
			if (++indegree[b] > 1) {
				isOK = false;
			}
		}
	}
	return 0;
}