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