问题描述
问题分析
涉及到树的知识
不过刚开始纠结在了输入数据的终止条件
然后看了几篇文章
也是大概懂了
也就是每次判断是以 0 0 作为结束
然后以 -1 -1 作为程序终止
那么思路
当满足不是树的条件时
记录不是树
直接等待所有当组数据输完
便可以断定不是树
否则继续进行操作
当输入数据为 0 0 时 进行判断是否为树
因为空树也是树
所以可以初始化标记为 true
伪代码应该写为:
(这种思考方法我觉得还是可取的)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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了~
不过以后或许会再来改善一下这个代码
这个写得太……
业余了？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #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;
}
|
题目地址:
【杭电】[1325]Is It A Tree?
【POJ】[1308]Is It A Tree?
【杭电】[1272]小希的迷宫