首页 > 代码库 > ouc 1059

ouc 1059

2024-08-02 09:16:34   213人阅读

1059: 树判断

时间限制: 1 Sec  内存限制: 64 MB
提交: 77  解决: 16
[提交][状态][讨论版]

题目描述

        树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树（tree）是包含n（0<=n<=1000）个结点的有穷集合，其中：  


        （1）每个元素称为结点（node）；   
        （2）有一个特定的结点被称为根结点或树根（root）；  
        （3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的结合T1，T2，……，Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。  

        树形结构示例如下图，圆表示节点，节点（1<=节点序号<=1000）之间的连线表示边，下图中前面的两个是树形结构，第3个不是。

 

 

 

输入

输入包含多个测试样例，每个样例使用一对数字表示两个有边的节点，如果两个节点为0表示样例结束。-1 -1 表示全部测试样例结束。

 

输出

每个测试样例输出 "Case k is a tree." 或者 "Case k is not a tree."，k 对应于测试样例的序号 。

 

样例输入

6 85 35 26 45 60 03 86 86 45 35 65 20 0-1 -1

样例输出

Case 1 is a tree.Case 2 is not a tree.

提示

 

来源

第二届“朗讯杯”高级组

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<algorithm>#include<queue>#include<vector>int x,y,set[100010],flag,cas,rt;int find(int x){return x==set[x]?x:set[x]=find(set[x]);}void Union(int x,int y){int ux,uy;ux=find(x),uy=find(y);if(ux!=uy)set[ux]=uy;}int main(){cas=0;while(1){flag=1,rt=0;cas++;memset(set,0,sizeof(set));while(scanf("%d%d",&x,&y)&&x!=0&&y!=0){if(x==-1&&y==-1) return 0;if(set[x]==0) set[x]=x;if(set[y]==0) set[y]=y;if(find(x)==find(y)) flag=0;else if(flag) Union(x,y);}for(int i=1;i<=100000;i++)if(set[i]==i)rt++;if(rt>1||!flag)printf("Case %d is not a tree.\n",cas);elseprintf("Case %d is a tree.\n",cas);}}

　　

ouc 1059


联系
我们