首页 > 代码库 > hdu-1272 小希的迷宫
hdu-1272 小希的迷宫
题目传送门
基础的并查集,稍微改下模板就可以。
要注意两个条件:
①判断合并的两个点根节点是否相同
②每个点能否全部连通
好像还有个问题,Yes 和 No。一开始把Yes和No全部都大写了,WA了几发 (..??_??..) 感觉应该不会有跟我一样的....
#include <iostream> using namespace std; int size[100010],tree[100010],vis[100010]; bool flag=true; void makeSet(int x) { size[x]=1; tree[x]=x; vis[x]=0; } int findSet(int x) { if(x!=tree[x]) tree[x]=findSet(tree[x]); return tree[x]; } void Union(int x,int y) { int fx=findSet(x); int fy=findSet(y); if(fx==fy) { flag=false; return; } if(size[fx]<size[fy]) { tree[fx]=fy; size[fy]+=size[fx]; } else { tree[fy]=fx; size[fx]+=size[fy]; } } int main(void) { int a,b; for(int i=0;i<100010;i++) makeSet(i); while(cin>>a>>b&&(a!=-1&&b!=-1)) { if(a==0&&b==0) { int k=0; for(int i=1;i<100010;i++) if(tree[i]==i&&vis[i]!=0) k++; if(k>1) flag=false; if(flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; for(int i=0;i<100010;i++) makeSet(i); flag=true; } if(a!=b) { Union(a,b); vis[a]=1; vis[b]=1; } } return 0; }
hdu-1272 小希的迷宫
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。