HDU 1325 || NYOJ 129 || POJ 1308 Is It A Tree?

题目链接~~>

做题感悟：做这个题首先要明白树的定义，在杭电做要认真读题终止条件不是等于 -1 -1 ,而是出现两个负数。

解题思路：树的定义：1.连通 2.不含圈 3 恰好有n -1 条边。（只有一个入度为 0 的点，其余点入读为 1），我开始做时让他们倒着指，这样每个节点只有一个父亲，只要判断是否有环和是否只有一个根节点。

代码（修改后的代码）：

      #include<stdio.h>
      #include<iostream>
      #include<map>
      #include<stack>
      #include<string>
      #include<string.h>
      #include<stdlib.h>
      #include<math.h>
      #include<vector>
      #include<queue>
      #include<algorithm>
      using namespace std ;
      #define LEN sizeof(struct node)
      const double PI = 3.1415926 ;
      const double INF = 99999999 ;
      const int MX =10005 ;
      int n ;
      bool flag,vis[MX] ;
      int father[MX],ru[MX] ;
      void init()
      {
      memset(vis,false,sizeof(vis)) ;// 用于标记是否出现过
      for(int i=1 ;i<MX ;i++)
       {
       father[i]=i ;
       ru[i]=0 ; // 用于统计入度
       }
      }
      int find(int x)
      {
      return father[x]==x ? x : father[x]=find(father[x]) ;
      }
      void union_find(int x,int y)
      {
       ru[y]++ ; // 入度加一
      if(ru[y]>1) flag=true ;// 如果入度大于1 则不是树
       vis[x]=vis[y]=1 ;
      int ax=find(x) ;
      int ay=find(y) ;
      if(ax!=ay)
       father[ax]=ay ;
      }
      int main()
      {
      int x,y,q=1 ;
      while(scanf("%d%d",&x,&y)&&(x>=0||y>=0)) // 没有仔细读题 -1 -1
       {
       init() ;// 初始化
       flag=false ;
      while(1)
       {
      if(!x&&!y)  break ;
      if(find(x)==find(y)||flag) // 如果已经在同一个集合||已经判断出来结果
       flag=true ;
      else union_find(x,y) ;
      scanf("%d%d",&x,&y) ;
       }
      if(flag)
      printf("Case %d is not a tree.\n",q++) ;
      else
       {
      int num=0 ;
      for(int i=1 ;i<=10000 ;i++) // 查找是否只有一个根节点
       {
      if(vis[i]&&father[i]==i)
       num++ ;
      if(num>1)
       {
       flag=true ;
      break ;
       }
       }
      if(flag)   printf("Case %d is not a tree.\n",q++) ;
      else printf("Case %d is a tree.\n",q++) ;
       }
       }
      return 0 ;
      }
  
 

原先代码~~>

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/22285453