GitBook

这里写图片描述 这里写图片描述

涉及到树的知识

不过刚开始纠结在了输入数据的终止条件 然后看了几篇文章 也是大概懂了

也就是每次判断是以 0 0 作为结束 然后以 -1 -1 作为程序终止

那么思路 当满足不是树的条件时 记录不是树 直接等待所有当组数据输完 便可以断定不是树 否则继续进行操作

当输入数据为 0 0 时 进行判断是否为树 因为空树也是树 所以可以初始化标记为 true

伪代码应该写为: (这种思考方法我觉得还是可取的)

bool flag=true;
int kase=0;
while(scanf("%d %d",&n,&m)!=EOF&&n>=0&&m>=0){
if(!flag&&!(n==0&&m==0))
continue;
if(n==0&&m==0){
……
if(flag)
printf("Case %d is a tree.",++kase);
else
printf("Case %d is not a tree.",++kase);
}
……
}

算了…… 还是掌握不了伪代码的精髓

是树的条件: 所有的节点只有一个指向它 所有节点的根都为同一个数 这个数的根是它本身

貌似表述不是很规范 不过大概就是这样了 还有一些特殊情况 考虑一下就好了

不过按照以前的写法会发现没有告诉一共有几个节点 所以用了一个数组进行记录

然后写的挺快的 不过因为思路不规范 加之各种原因 调试过程异常艰难 也确实出现了有的OJ能过 有的不能过的现象……

杭电据说存在 1 2 3 2 0 0 这种的 按照之前我的判定方法确实会WA POJ据说是有n,m相等的输入

总之这一题…… 对我貌似确实有点难度 好在也是AC了~ 不过以后或许会再来改善一下这个代码

这个写得太…… 业余了?

#include<stdio.h>
#include<string.h>
int par[10200];
int rank[10200];
int x[10200];
bool flag;
int find(int m) {
	if(m==par[m])
		return m;
	else
		return par[m]=find(par[m]);
}
void unite(int x,int y) {
	x=find(x);
	y=find(y);
	if(x==y)
		return;
	if(rank[x]<rank[y])
		par[x]=y;
	else {
		par[y]=x;
		if(rank[x]==rank[y])
			rank[x]++;
	}
}
void chu() {
	for(int i=1; i<10200; i++) {
		par[i]=i;
		rank[i]=0;
	}
	memset(x,0,sizeof(x));
	flag=true;
}
int main() {
	int n,m;
	int kase=0;
	chu();
	while(scanf("%d %d",&n,&m)!=EOF&&n>=0&&m>=0) {
		if(!flag&&!(n==0&&m==0))
			continue;
		if(n==0&&m==0) {
			int t;
			bool fir=true;
			for(int i=1; i<10200; i++) {
				if(!x[i])
					continue;
				if(fir) {
					t=find(i);
					fir=false;
				}
				if(find(i)!=t) {
					flag=false;
					break;
				}
			}
			if(flag&&find(t)!=t)
				flag=false;
			if(flag)
				printf("Case %d is a tree.\n",++kase);
			else
				printf("Case %d is not a tree.\n",++kase);
			chu();
		}
		if(!(n==0&&m==0)&&(n==m||(n!=m&&find(n)==find(m)))) {
			flag=false;
		} else {
			if(x[m]==2) {
				flag=false;
			} else {
				x[n]=1;
				x[m]=2;
				unite(n,m);
			}
		}
	}
	return 0;
}

题目地址: 【POJ】[1308]Is It A Tree? 【杭电】[1325]Is It A Tree? 【杭电】[1272]小希的迷宫