首页 > 代码库 > HDU 1325 Is It A Tree? (POJ 1308)
HDU 1325 Is It A Tree? (POJ 1308)
并查集问题。。。
这题以前做过……
以前做过……
做过……
过……
不过重做时候被吭得异常之爽……
在判断 vis[i]的时候。我记得标准C++是非0 即为真。
而我用C++ 提交的时候 if(vis[i]) 去直接给我WA了。
用G++ 就AC了。。。然后改成if(vis[i]==1) 交C++ 就AC了。
特瞄的我每次初始化都把 vis[i] 都赋值为 0 了。。都能出这种错?
求路过大神明示我的错误。
题意是判断是否是一棵树。
不能存在森林,用并查集合并,每个点的入度不能超过1.
比如 1 2 3 2 0 0 就不是一棵树。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int fa[10010]; bool vis[10010]; int in[10010]; int father(int x) { if(fa[x]!=x) fa[x]=father(fa[x]); return fa[x]; } void intt() { for(int i=0;i<=10010;i++) fa[i]=i,vis[i]=in[i]=0; } int main() { intt(); int x,y; bool flag=1; int tmp=0; int treecot=1; while(scanf("%d%d",&x,&y)) { if(x<0&&y<0)return 0; tmp=max(tmp,max(x,y)); if(x==0&&y==0) { int cot=0; for(int i=0;i<=tmp;i++) { if(vis[i]==1&&father(i)==i)cot++;//非常之坑爹! if(in[i]>1||cot>1)flag=0; if(!flag)break; } if(flag)printf("Case %d is a tree.\n",treecot++); else printf("Case %d is not a tree.\n",treecot++); intt(); flag=1,tmp=0; } else { if(!flag)continue; int fx=father(x); int fy=father(y); if(fx==fy)flag=0; else { fa[fy]=fx,in[y]++; vis[x]=vis[y]=1; } } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。