并查集和树的一些性质 hdu1325
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1325
题意是每次输入一对数字n，m表示一条树边，并且n是m的父亲，直到n==0&&m==0，表示这一组数据结束输入，当某组数据第一条边n，m都是-1时结束程序，我表达不太行。
我们要判断每一组数据输入的这些边是不是可以构成一棵树。
首先如果这时一棵树，我们可以知道它的一些性质，比如：
除了根节点入度为0，其他点的入度都为1。
边的数目加1等于点的数目
树上的点是两两连通的。
那么我们只需要记录每个点的入度（是不是大于1），记录边数和点数，最后判断这是不是一棵树（连通），而不是森林。
这里需要注意空树也是树。
我的代码写的有点low：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 100005 /*struct point{ int u,w; }; bool operator <(const point &s1,const point &s2) { if(s1.w!=s2.w) return s1.w>s2.w; else return s1.u>s2.u; }*/ bool vis[maxn]; int pre[maxn],in[maxn]; int n,m,k,t; int edge_num,point_num,flag,digit;//digit在这里是随便记录一个树上面的点，后面好判断连通 void init() { for(int i=0;i<maxn;i++) pre[i]=i; memset(vis,false,sizeof(vis)); memset(in,0,sizeof(in)); edge_num=point_num=0; flag=0; } int find(int a)//找祖先节点 { if(pre[a]==a) return a; return pre[a]=find(pre[a]); } void combine(int a,int b)//连接两个集合 { int x=find(a); int y=find(b); if(x!=y) pre[x]=y; } void addedge(int a,int b)//添加边 { if(!vis[a]) { digit=a; vis[a]=true; point_num++; } if(!vis[b]) { vis[b]=true; point_num++; } edge_num++;//边加 in[b]++;//入度加 if(in[b]>1) flag=1; combine(a,b); } int jug()//判断是否是数 { if(flag) return false; if(edge_num+1!=point_num) return false; for(int i=0;i<maxn;i++) { if(vis[i]&&find(digit)!=find(i)) return false; } return true; } int main() { int num=0; while(scanf("%d%d",&n,&m)) { if(n<0||m<0) break; if(n==0&&m==0)//特殊情况，空树 { printf("Case %d is a tree. ",++num); continue; } init(); addedge(n,m); while(scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; addedge(n,m); } if(jug()) printf("Case %d is a tree. ",++num); else printf("Case %d is not a tree. ",++num); } return 0; }