A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.
There is exactly one node, called the root, to which no directed edges point.
Every node except the root has exactly one edge pointing to it.
There is a unique sequence of directed edges from the root to each node.
For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.
In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.
Input
The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.
Output
For each test case display the line “Case k is a tree.” or the line “Case k is not a tree.”, where k corresponds to the test case number (they are sequentially numbered starting with 1).
Sample Input
6 8 5 3 5 2 6 4
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
Sample Output
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
意思就是给你多组数
第一组
6 8:结点6→结点8,结点6是结点8的上一层
5 3:结点5→结点3,结点5是结点3的上一层
5 2:……
6 4:……
5 6:……
0 0:该组输入结束
第二组……
然后判断这些数及其之间的关系是否构成一棵树
可以用并查集及树的定义
树的定义:树(tree)是包含n(n>=0)个结点的有穷集,其中
1.每个元素称为结点(node)
2.有一个特定的结点被称为根结点或树根(root)
3.除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1,T2,……Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)(人话的意思就是根到某个结点的路径只有一条)
是树的特殊情况:
1.空树:0 0
不是树的情况:
1.形成环:1 2 2 3 3 4 4 1 0 0
2.两个结点重复输入:1 2 1 2 0 0
3.两个结点反过来重复输入:1 2 2 1 0 0
4.结点自己连自己:1 2 2 2 0 0
5.有多棵树的森林(多个根):1 2 3 4 0 0
6.根到某个结点的路径有多条(入度>1):1 2 2 3 1 3 0 0
注意:若是判断根数来判断是否为树,则注意空树和单个环的根数都为0
#include<stdio.h> #include<cstring> using namespace std; struct trees { int p[100000];//[]里面是结点,p[]是该结点的上一层相连的结点,根为最高层 int c[100000];//[]里面是结点,c[]是该结点的入度 int r;//根个数 trees()//初始化 { int i; r=0; memset(c,0,sizeof(c)); for(i=0;i<100000;i++) p[i]=i; //每组数据的每个结点初始根设为自己,后面输入结点后对应结点便会合并为同根,即最后输出时只有根和未输入的结点的根为自己 } }tree; bool b[100000],o;//b[0]单独用于判断是否为树,b[n](n>0)记录有无对应的结点n,o判断是否为空树 void init();//初始化函数 void change(int&,int&,int&);//输入数据后更新树的数据,入度c,连接关系p,记录结点出现b int root(int,int&);//对某结点寻根 int main() { int i,n,m,x,y,z=0,k=0;//i临时的循环进度,n结点→m结点,x和y存n和m的根,z为序号最大的结点(最后循环的上限) memset(b,false,sizeof(b)); scanf("%d%d",&n,&m); o=true;//先认为为空树,空树是直接输入0 0的,直接输出 for(b[0]=true;n!=-1&&m!=-1;scanf("%d%d",&n,&m))//先认为是树,否则无法通过if if(b[0]&&n>0&&m>0) { o=false;//输入过非0的数,判断为非空树 x=root(n,tree.p[n]); y=root(m,tree.p[m]); if(n==m||(n!=m&&x==y))//自己连自己或是已经同根即入度>1,根去往结点路径不止一条 { b[0]=false; continue; } change(n,m,z);//通过判断,存入数据 if(tree.c[m]>1)//立刻判断m入度个数,避免之后进行无意义的计算 { b[0]=false; continue;//其实可以去除这句…… } } else if(n==0&&m==0) { k++;//答案第几棵树 if(!b[0])//如果不是树 { printf("Case %d is not a tree.\n",k); init(); } else { for(i=1;i<=z;i++)//判断根个数,是否为森林或是成环了 if(b[i]==true&&tree.p[i]==i)tree.r++;//在结点存在的情况下根为他自己则根个数加1 if(tree.r!=1&&!o)printf("Case %d is not a tree.\n",k); //根个数不对并且非空树(成一个环和空树的根个数都是0) else printf("Case %d is a tree.\n",k); init(); } } return 0; } int root(int p,int &r) { if(r!=p)return r=root(r,tree.p[r]);//r为上一层的结点,p为被指向的结点 //赋值是缩短路径便于以后寻根,对是否为树无影响因为:都是只有一条路径且根个数不变 return p;//return r也行 } void init()//初始化 { tree=trees(); memset(b,false,sizeof(b)); b[0]=true; o=true; } void change(int &n,int &m,int &z) { if(z<(n>m?n:m))z=n>m?n:m;//存最大结点序号,最后判断根个数循环的循环上限 b[n]=true;//点n,m存在 b[m]=true; tree.p[m]=n;//m上层连接的点为n tree.c[m]++;//m是被指向的,入度加1 }