学步园

题目来源: http://acm.pku.edu.cn/JudgeOnline/problem?id=1308

解题报告:

首先判断这些点是否属于同一个集合: 如果两个点之间有边相连,则它们属于同一个集合

接着,判断是否存在一个点入度为0,即根

再判断,除了根以外的点,是否入度都为1,

如果满足上述条件,则为树.

#include <iostream><br /> using namespace std;</p> <p>int cnt=0;</p> <p>typedef struct _node<br /> {<br /> int key;<br /> int rank;<br /> int degree;<br /> _node* parent;<br /> }node;</p> <p>node **s;</p> <p>node* find(int a)<br /> {<br /> for(int i=0;i<cnt;i++)<br /> if(a==(s[i]->key))<br /> return s[i];<br /> return NULL;<br /> }</p> <p>void makeSet(int a)<br /> {<br /> if(find(a)==NULL)<br /> {<br /> s[cnt]=new node;<br /> s[cnt]->key=a;<br /> s[cnt]->parent=s[cnt];<br /> s[cnt]->degree=0;<br /> s[cnt]->rank=0;<br /> cnt++;<br /> }<br /> }</p> <p>node* findSet(node* a)<br /> {<br /> if(a->parent!=a)<br /> a->parent=findSet(a->parent);<br /> return a->parent;<br /> }</p> <p>void link(node* x, node * y)<br /> {<br /> if(x->rank > y->rank)<br /> y->parent=x;<br /> else<br /> {<br /> x->parent=y;<br /> if(x->rank==y->rank)<br /> y->rank++;<br /> }<br /> }</p> <p>void _union(int a,int b)<br /> {<br /> node *s=find(b);<br /> s->degree++;<br /> link(findSet(find(a)),findSet(s));<br /> }</p> <p>int main()<br /> {<br /> int caseNum=0;<br /> int a,b;<br /> s=new node*[10001];<br /> while(1)<br /> {<br /> scanf("%d%d",&a,&b);<br /> if(a==-1 && b==-1)<br /> break;<br /> else if(a==0 && b==0)<br /> {<br /> int n1=0,n2=0,n3=0;<br /> bool judge=true;<br /> for(int i=0;i<cnt;i++)<br /> {<br /> if(s[i]->parent==s[i])<br /> n1++;//集合个数<br /> if(s[i]->degree==0)<br /> n2++;//入度为0的个数<br /> if(s[i]->degree==1)<br /> n3++;//入度为1的个数<br /> }<br /> if(cnt!=0 && (n1!=1 || n2!=1 || n3!=cnt-1))<br /> judge=false;<br /> if(judge)<br /> cout << "Case " << ++caseNum << " is a tree." << endl;<br /> else<br /> cout << "Case " << ++caseNum << " is not a tree." << endl;<br /> cnt=0;<br /> }<br /> else<br /> {<br /> makeSet(a);<br /> makeSet(b);<br /> _union(a,b);<br /> }<br /> }<br /> delete [] s;<br /> return 0;<br /> }

附录:

Description

Input

Output

Sample Input

6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0
-1 -1

Sample Output

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.