【包教包会】用树的定义去判断树！(HDU1272)(HDU1325)(POJ1308)

标题这几题都是去判断树的，只是输出不一样

要用定义去做树，那肯定要知道树是什么
学习的时候很迷茫是没搞清楚大方向
什么是大方向呢？
两个字：图论
树肯定是图，但图不一定是树
搞清楚这么几个知识点就可以愉快的做这题了

什么是度？度就是边。度分为入度和出度(出边和入边)。我们这里有个点V，指向V的边就是入度，从V指出去的是出度 什么是树？只有一个点入度为0，其它点入度为1的图就是树。

好了，一旦解决了什么是树，那所有问题解决了。什么？你说还不懂？那我给你一个个列出来

只有一个点入度为0保证了树有且只有一个根节点 除根节点外，其它点都有入度，保证了这一定是个连通图（仔细想就知道了，有入度肯定连着） 除根节点外，其它点的入度都是1，保证每个点的根节点只有一个（这也保证了图不可能有环）

所以呢，并查集也可以做这题，操作就是：

连通分量为1 (Find(i) == i的数量只有1) 且图无环。(在合并操作里面可以判断)

当然了，这题有个很鬼的地方----就是没有点也算树。
讲道理图不可能是空集，既然出题人觉得 空即是色 的话，那就加个特判吧……

这里先列出用树的性质做的代码。

#include ///注意poj不能用万能头，自行更改吧 using namespace std; int T,n,a,b; int e[100005];///入度 int book[100005];///标记这个点是否出现 int main() { int mx=0;///我要遍历存在的点。。这里是用数组下标，所以我要保存遍历到哪里 int cnt=1;///这个just是用来输出的时候看是第几个例子而已……不用管 int isp=1;///这就是判断是不是空集的标记 while(scanf("%d%d",&a,&b)!=EOF) { if(a+b<0)break;///-1 -1的时候结束 if(a==0 && b==0)///两个都是0的时候判断 { int ans=0;///入度为0的个数（有几个根，很明显只能有一个根） int flag=1;///是否除了根节点以外都是入度为1的呢？ for(int i=1;i<=mx;i++) { if(book[i] && e[i]==0)///判断出现并且入度为0，那就是根 { ans++; } else if(book[i] && e[i]!=1)///不是根，那就判断入度是不是1 { flag=0; } } ///hdu 1272的只有输出不一样！(HDU1325)(POJ1308)都是这个板子 if((flag==1 && ans==1) || isp)printf("Case %d is a tree.\n",cnt); else printf("Case %d is not a tree.\n",cnt); ///这些都是初始化 memset(e,0,sizeof(e)); memset(book,0,sizeof(book)); mx=0; cnt++; isp=1; } else{ isp=0; e[b]++;///入度 book[a]=1;///标记这个点是否出现 book[b]=1; mx=(max(a,max(mx,b))); } } return 0; }
作者：AutoLoop255

poj hdu