又是一个并查序的问题,这里有两方面
1:必须是并查集
2:满足点的个数比边数多一
URL:http://acm.hdu.edu.cn/showproblem.php?pid=1272
代码如下
#include<stdio.h> #include<algorithm> #define M 100010 using namespace std; int father[M], mark[M]; int flag; void init() { for(int i=0;i<M;i++) { father[i]=i; mark[i]=0; } } int getfather(int r) { int n=r; while(n!=father[n]) n=father[n]; return n; } void Union(int x,int y) { int rootx=getfather(x); int rooty=getfather(y); if(rootx!=rooty) father[rootx]=rooty; } int main() { int a,b,i; while(scanf("%d%d",&a,&b)!=EOF && (a!=-1 || b!=-1)) { if(a==0 && b==0) { printf("Yes\n"); continue; } init(); int max=-1,min=M,num=0; flag=0; while(a||b) { if(a>max) max=a; if(b>max) max=b; if(a<min) min=a; if(b<min) min=b; mark[a]=1;mark[b]=1; int aa=getfather(a); int bb=getfather(b); if(aa==bb) flag=1; else Union(aa,bb); scanf("%d%d",&a,&b); } if(flag==1) printf("No\n"); else { for(i=min;i<=max;i++) // 这里的min和max就是上面的计算的范围,减少没必要的搜索 { if(mark[i]==1 && father[i]==i) // mark就是说在for循环里面有这个数字 num++; } if(num==1) printf("Yes\n"); else printf("No\n"); } } return 0; }