1308.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"

void main()
{int x,y,b[100][100],n[100],m,i,j,tree,k,root,now,temp,cas;
cas=1;
while(1)
{
	m=0;
 tree=1;


while(1)
{cin>>x;
cin>>y;
if(x==0||x==-1)break;
if(x==y)tree=0;

for(i=0;i<m;i++)if(n[i]==x)break;
if(i==m){n[i]=x;m++;for(k=0;k<m;k++){b[i][k]=0;b[k][i]=0;}}
for(j=0;j<m;j++)if(n[j]==y)break;
if(j==m){n[j]=y;m++;for(k=0;k<m;k++){b[j][k]=0;b[k][j]=0;}}

b[i][j]++;if(b[i][j]>1){tree=0;}
}//
/*for(j=0;j<m;j++)cout<<n[j]<<' ';cout<<endl;
for(i=0;i<m;i++)
{for(j=0;j<m;j++)cout<<b[i][j]<<' ';cout<<endl;}*/

if(x==-1)break;
if(tree&&m!=0)
{root=0;
    for(i=0;i<m;i++)n[i]=0;	
    
	for(i=0;i<m;i++)
	{k=0;
	for(j=0;j<m;j++)if(b[j][i]!=0){k++;n[i]=j;}
	if(k>1){tree=0;break;}
	else if(k==0&&(root!=0)){tree=0;break;}
	else if(k==0&&root==0)root++;
	}
	if(root==0)
	{tree=0;}
	
	if(tree)
	{	for(i=0;i<m;i++)
	    if(n[i]!=-1){
		now=i;
		while(n[now]!=0&&n[now]!=-1){if(n[now]==i){tree=0;break;}else temp=n[now];n[now]=-1;now=temp;}
		if(!tree)break;	
					}
	}
}
if(tree)cout<<"Case "<<cas<<" is a tree."<<endl;
else cout<<"Case "<<cas<<" is not a tree."<<endl;
cas++;
};
}