| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:2 1 3 1 4 1 是不是树???没有方向??In Reply To:2 1 3 1 4 1 是不是树???没有方向?? Posted by:fff123 at 2011-04-07 15:33:47 > 谁告诉我啊。。。。2 1 3 1 4 1 是不是树???????????
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1000
int father[N],node[N];
void init(void)
{
int i;
for(i=0;i<N;i++)
{
father[i]=i;
node[i]=0;//标记出现的节点
}
return ;
}
int getfather(int x)
{
if(x!=father[x])
{
father[x]=getfather(father[x]);
}
return father[x];
}
void uniontree(int x,int y)
{
int p, q;
p=getfather(x);
q=getfather(y);
if(q==p)
return ;
father[p]=q;
return ;
}
int main(void)
{
int a,b,i,t=1,tag,root;
while(1)
{
scanf("%d%d",&a,&b);
if(a==-1&&b==-1)
break;
if(a==0&&b==0)//null tree
{
printf("Case %d is a tree.\n",t++);
continue;
}
init();
node[a]=node[b]=1;
root=a;
tag=1;
if(a==b)//指向自己的不是树
tag=0;
else
uniontree(a,b);
while(scanf("%d%d",&a,&b)&&!(a==0&&b==0))
{
if(getfather(a)==getfather(b))//祖先相同,肯定有环
tag=0;
uniontree(a,b);
node[a]=node[b]=1;
}
if(tag==1)
{
root=getfather(root);
for(i=0;i<N;i++)
{
if(node[i]&&getfather(i)!=root)//祖先必须相同,否则就是森林
tag=0;
}
}
printf("Case %d is ",t++);
if(tag==1)
printf("a tree.\n");
else
printf("not a tree.\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator