NYOJ--树的判定

- 日理万妓 2022-08-26 15:18 138阅读 0赞

## 树的判定 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 4

描述

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.

![20111014112815_95730.jpg][]

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.

输入

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.  
  
The number of test cases will not more than 20,and the number of the node will not exceed 10000.  
The inputs will be ended by a pair of -1.

输出

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).

样例输入

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

样例输出

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

来源

[POJ][]

解析：输入的是两个整数为一对每个整数表示节点编号，同时这两个节点之间有一条边存在，且是由第一个节点指向第二个节点，英文的大致内容就是去判定输入的内容是否能组成一颗树。

首先直接输入0 0表明此时是一颗空树，应该输出is a tree.

当出现节点自己到自己之间的边时，应该输出 is not a tree.

如果输入的边与节点的数量不满足edge=vex-1的话也是不属于树的

另外当输入的树中出现环的话也是不属于树

以上这些情况都要考虑到。

其实自己也是看了其他人的博客自己写的代码。

开始本人是这样考虑的，要想组成一颗树，满足了节点和边的条件外，只要输入的节点中只有一个节点的入度是0，其他的节点的入度是零就OK了(有同学跟我一样这么想么？)

如果按照上面这样想的话我画个草图就明白自己为什么wa了哈

![20140418212807875][]

上面这个草图满足节点和边的条件，也满足入度出度的情况，但是很明显这不是一颗树。

应该是用到并查集的知识(自己对这点还没有深刻的理解)

除了考虑空树和节点与边之间的关系外，还要得到输入每条边两个节点的最顶上的父亲节点也就是并查集中的Find函数，为什么要这么做类？因为如果x，y两个节点的父节点相同则肯定不是树，因为环就是这种情况。同时还要检查y节点的父节点是不是本身，也就是说x指向的这个节点(y)是否已经有节点指向了它，如果有节点指向了它，此时再有节点指向它则违反了树中入度大于1的规则，可见并查集是多么的有用有效。

推荐关于并查集的一个博文[http://hi.baidu.com/czyuan\_acm/item/13cbd3258c29e20d72863edf][http_hi.baidu.com_czyuan_acm_item_13cbd3258c29e20d72863edf](czyuan原创)

下面贴一下自己的代码

#include <iostream>
    #include <memory.h>
    using std::endl;
    using std::cin;
    using std::cout;
    int Parent[10000];
    int Visit[10000];
    //并查集,得到父亲节点
    int getParent(int x)
    {
    	if(Parent[x]==0)
    		return x;
    	else
    		return getParent(Parent[x]);
    }
    int main()
    {
    	int x,y;
    	int cnt=1;
    	//记录节点的个数和边的个数
    	int vex,edge;
    	while(cin >> x >> y)
    	{
    		//判断是否为树的标志
    		bool flag=true;
    		vex=0;
    		edge=0;
    		//重置数据
    		memset(Parent,0,sizeof(Parent));
    		memset(Visit,0,sizeof(Visit));
    		//终止循环
    		if(x==-1&&y==-1)
    			break;
    		if(x==y)
    		{//自己到自己的边，肯定不是树
    			flag=false;
    		}
    		if(x!=y)
    		{
    			//节点和边增加
    			vex+=2;
    			edge++;
    			Visit[x]=Visit[y]=1;
    			Parent[y]=x;
    		}
    		if(x==0&&y==0)
    		{//第一组数据表明此时为空树，空树也是树
    			cout << "Case " << cnt <<" is a tree." << endl;
    			cnt++;
    			continue;
    		}else{
    			while(cin >> x >> y)
    			{
    				if(x==0&&y==0)
    					break;
    				if(x==y)
    				{
    					flag=false;
    					continue;
    				}
    				if(!Visit[x])
    				{
    					vex++;
    					Visit[x]=1;
    				}
    				if(!Visit[y])
    				{
    					vex++;
    					Visit[y]=1;
    				}
    				//找x和y的最顶上的祖先节点
    				int m=getParent(x);
    				int n=getParent(y);
    				//判断是否为树
    				//m==n的情况是出现环状指向了同一个父亲节点的情况，此时组成的边也可能节点数满足关系，当此时不是树
    				//n!=y的情况是y此时已经有父亲节点此时又有一个节点指向了y，也就是树中不存在入度大于一的节点
    				if(m==n||n!=y)
    				{
    					flag=false;
    					continue;
    				}
    				Parent[n]=m;
    				edge++;
    			}
    		}
    		if(!flag||edge!=vex-1)
    		{
    			cout << "Case " << cnt << " is not a tree." << endl;
    			cnt++;
    		}else{
    			cout << "Case " << cnt << " is a tree." << endl;
    			cnt++;
    		}
    	}
    	return 0;
    }

[20111014112815_95730.jpg]: http://acm.nyist.edu.cn/JudgeOnline/admin/kind/attached/20111014112815_95730.jpg
[POJ]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=POJ
[20140418212807875]: /images/20220824/b26773f3bb3a4ad7a570dcb3684d05f2.png
[http_hi.baidu.com_czyuan_acm_item_13cbd3258c29e20d72863edf]: http://hi.baidu.com/czyuan_acm/item/13cbd3258c29e20d72863edf