hdu 1257 小希的迷宫并查集

2019-11-06 08:13:49

字体：大中小

来源：转载

供稿：网友

题目链接:

http://acm.hdu.edu.cn/showPRoblem.php?pid=1272

题意:

题解:

用并查集来判断是否都在一个集合里面，是否成环，就好了

代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 1e5+10;int mark[maxn],fa[maxn];int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]);}bool Union(int u,int v){ int t1 = find(u), t2 = find(v); if(t1 == t2) return false; fa[t1] = t2; return true;}int main(){ int a,b; while(scanf("%d%d",&a,&b)){ if(a==-1 && b==-1) break; if(a==0 && b==0){ puts("Yes"); continue; } MS(mark); for(int i=0; i<=maxn; i++) fa[i] = i; mark[a] = mark[b] = 1; fa[a] = b; int flag = 1; while(scanf("%d%d",&a,&b) && (a+b)){ mark[a] = mark[b] = 1; if(Union(a,b)==0) flag = 0; } if(flag==0) puts("No"); else{ int cnt = 0; for(int i=1; i<=maxn; i++){ if(mark[i] && fa[i]==i) cnt++; } if(cnt == 1) puts("Yes"); else puts("No"); } } return 0;}

上一篇：eclipse快捷键包括查找类、方法、变量

下一篇：golang cache 源码学习