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