POJ-Is It A Tree?

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.

这道题其实就是考察你对树的理解

刚开始我不是很了解树，有很多情况都没有考虑进去

1.无环

2.除了根，所有入度为1

3.这个结构只有一个根

其实根据这几条特性水一下就行了，连并查集都不用

但是在学习并查集，还是用一下并查集吧！

其中 0 0 也是树，是一个空树！

下面有几种情况，如果这几种情况都考虑了，那么基本就AC了

1.     0 0     空树是一种树

2.      2   2   0  0    不能指向自己！这个不是树

3.     1 2 1 2 0 0  不是树

4.     1 2 2 3 4 5    不是树

5 .    1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 因为一个节点指向了根节点，这就是错误了，形成环了

6       1 2 2  1 0 0 也不是树 

#include<stdio.h> #include<string.h> #define inf 99999999 int id[105]; int vis[105]; bool book[105]; int a,b,min,flag,step=1,num=0,first=0; void csh() { step++; flag=0; first=0; num=0; memset(vis,0,sizeof(vis)); memset(book,false,sizeof(book)); for(int i=0; i<=100; i++) { id[i]=i; } } int find(int a) { while(a!=id[a]) { //id[a]=id[id[a]]; a=id[a]; } return a; } void join(int a,int b) { int root1=find(a); int root2=find(b); if(root1!=root2) { id[root2]=root1; } } int main() { memset(vis,0,sizeof(vis)); memset(book,false,sizeof(book)); for(int i=0; i<=100; i++) { id[i]=i; } while(scanf("%d%d",&a,&b)) { first++; if(a==0&&b==0&&first==1) { printf("Case %d is a tree.\n",step); csh(); continue; } if(a==-1&&b==-1) { break; } if(a==0&&b==0) { for(int i=1; i<=100; i++) { if(book[i]==true) { min=find(i); //printf("%d\n",find(i)); break; } } for(int i=1; i<=100; i++) { if(book[i]==true&&find(i)!=min) { flag=1; } if(book[i]==true&&vis[i]>1) { flag=1; } if(book[i]==true&&vis[i]==0) { num++; } } if(num<1) { flag=1; } if(flag!=1) { printf("Case %d is a tree.\n",step); } if(flag==1) { printf("Case %d is not a tree.\n",step); } csh(); continue; } if (a!=0&&b!=0) { if(a==b) { flag=1; } join(a,b); book[a]=true; book[b]=true; vis[b]++; } } return 0; } 题目中也没有说有多少个数

我试了100，过了

还有输入问题，我也想了一会，这种输入还是不是熟练

下面上一下大神代码，看一下敌我差距

/*不能算是并查集，只是用了路径压缩和树的特点， 和1272的区别在于它是有向图，它的父结点是固定的*/ #include <iostream> using namespace std; int main() { int n,m,k=0,s[100005]={0},j=0,i,big; bool f=0; bool flag[100005]={0}; while(cin>>n>>m) { if(m==-1&&n==-1)return 0; if(m==0&&n==0) { k++; int c=0; for(i=1;i<=big;i++){if(flag[i]){c++;flag[i]=0;s[i]=0;}} if(f) cout<<"Case "<<k<<" is not a tree."<<endl; else if(c==0)cout<<"Case "<<k<<" is a tree."<<endl; else if(c!=j+1)cout<<"Case "<<k<<" is not a tree."<<endl; else cout<<"Case "<<k<<" is a tree."<<endl; j=0; f=0; big=0; } else { j++; flag[n]=flag[m]=1; if((m>n?m:n)>big)big=(m>n?m:n); //如果已经有父结点，但是父结点不是n，那就是不树了 if(s[m]!=0&&s[m]!=n)f=1; else s[m]=n; } } return 0; }

其实大神根本就没有用并查集

你只需要记录每个点的入度，，入度为0的点必定只有一个，多了说明不是一个数

少了说明最后连成一个环了。

如果有入度大于1的也是形成环了。根本用不到并查集。