学步园

判断是不是一颗树，简单的并查集

只要注意几种情况就可以了：

1. 0 0  空树也是树

2. 1 1 不是树，自己不能指向自己

3. 1 2 2 1 不能形成环

4. 1 2 3 4 森林不是树

其实只要注意0 0,其它的几种情况就是树的定义/*<br /> * File: main.cpp<br /> * Author: mi<br /> *<br /> * Created on 2011年2月20日, 下午8:42<br /> */<br /> #include <cstdlib><br /> #include <stdio.h><br /> #include <string.h><br /> #define N 150<br /> using namespace std;<br /> /*<br /> *<br /> */<br /> int father[N],rank[N];<br /> void make_set()<br /> {<br /> int i;<br /> for(i=1;i<150;i++)<br /> {<br /> father[i]=i;<br /> rank[i]=0;<br /> }<br /> }<br /> int find_set(int x)<br /> {<br /> if(x!=father[x])<br /> father[x]=find_set(father[x]);<br /> return father[x];<br /> }<br /> void Union(int x,int y)<br /> {<br /> int rootx=find_set(x),rooty=find_set(y);<br /> if(rootx==rooty)<br /> return ;<br /> father[rooty]=rootx;<br /> }<br /> int main(int argc, char** argv)<br /> {<br /> int a,b,c=1,flag,first;<br /> while(scanf("%d%d",&a,&b)&&(a>=0||b>=0))<br /> {<br /> if(a==0&&b==0)<br /> {<br /> printf("Case %d is a tree./n",c++);<br /> continue;<br /> }<br /> memset(father,0,sizeof(father));<br /> memset(rank,0,sizeof(rank));<br /> flag=0;<br /> make_set();<br /> rank[a]=rank[b]=1;<br /> first=a;<br /> if(a==b)<br /> flag=1;<br /> else<br /> Union(a,b);<br /> while(scanf("%d%d",&a,&b)&&(a||b))<br /> {<br /> int rootx=find_set(a),rooty=find_set(b);<br /> rank[a]=rank[b]=1;<br /> if(rootx==rooty)<br /> flag=1;<br /> else<br /> Union(a,b);<br /> }<br /> for(int i=1;i<150;i++)<br /> if(rank[i]&&find_set(i)!=find_set(first))<br /> flag=1;<br /> if(flag)<br /> printf("Case %d is not a tree./n",c++);<br /> else<br /> printf("Case %d is a tree./n",c++);<br /> }<br /> return 0;<br /> }<br />