本文主要是介绍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 ;
}原先代码~~>
这篇关于HDU 1325 || NYOJ 129 || POJ 1308 Is It A Tree?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
