题目大意：
判断给定的数对是否构成一棵树，
解决：并查集
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4 int num[10005];
5 bool outdegree[10005];
6 bool mark[10005];//标记该结点是树的一个结点
7 int find(int x)//并查集的查找
8 {
9 if(num[x]<0)return x;
10 return num[x]=find(num[x]);
11 }
12 bool merge(int a,int b)//并查集的合并，并非标准合并程序，根据需要改动
13 {
14 if(outdegree[b])return false;//若为树，每个非根节点的出度一定为1，若出度已经为1，则直接判断不为树
15 outdegree[b]=1;
16 mark[a]=mark[b]=1;
17 int fa=find(a);
18 int fb=find(b);
19 num[b]=a;//将b为根的树接到a上
20 return true;
21 }
22 int main()
23 {
24 int a,b,icase=1;
25 while(cin>>a>>b,a!=-1&&b!=-1)
26 {
27
28 if(a==0&&b==0)
29 {
30 cout<<"Case "<<icase++<<" is a tree."<<endl;
31 continue;
32 }
33 int ok=true,min=10005,max=0,nroot=0;
34 memset(mark,0,sizeof(mark));//这个地方很重要，必须初始化
35 memset(num,0xff,sizeof(num));
36 memset(outdegree,0,sizeof(outdegree));
37 do
38 {
39 if(!merge(a,b)){ok=false;continue;}
40 if(a<min)min=a;//这四句话是找出最大和最小的边的区间范围
41 if(b<min)min=b;
42 if(a>max)max=a;
43 if(b>max)max=b;
44
45 }while(cin>>a>>b,a||b);
46
47 if(!ok)cout<<"Case "<<icase++<<" is not a tree."<<endl;
48 else
49 {
50 for(int i=min;i<=max&&nroot!=2;i++)
51 if(mark[i] && num[i]<0 )nroot++;//数数结点中根的个数
52 if(nroot==1)cout<<"Case "<<icase++<<" is a tree."<<endl;
53 else cout<<"Case "<<icase++<<" is not a tree."<<endl;
54 }
55 }
56 // system("pause");
57 return 0;
58 }