小希的迷宫-HDU-1272（并查集 or 树性质）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

//并查集 #include<bits/stdc++.h> using namespace std; int pre[100001]; int find(int root){ int son,t; son=root; while(root!=pre[root]) root=pre[root]; while(son!=root){ t=pre[son]; pre[son]=root; son=t; } return root; } void join(int a,int b){ int x=find(a),y=find(b); if(x!=y) pre[y]=x; } int main(){ int a,b,flag,i,sum; while(1) { flag = 0; while(~scanf("%d%d",&a,&b) && a!=0 && b!=0){ if(a==-1 && b==-1) return 0; if(pre[a]==0)pre[a]=a; if(pre[b]==0)pre[b]=b; if(find(a)==find(b))flag = 1; else if(flag!=1) join(a,b); } for(sum = 0,i=1;i<100001;i++){ if(pre[i]==i)sum++; pre[i] = 0; } if(sum>1 || flag == 1) printf("No\n"); else printf("Yes\n"); } } //1 2 3 4 0 0 No 没有连通 //0 0 Yes //1 1 0 0 No（该代码）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

//树性质 #include <stdio.h> bool s[100001]; int main() { int a,b,i,len,num,v; for(i=0;i<100001;++i) s[i]=false; len=0,num=0,v=0; while(1) { scanf("%d%d",&a,&b); if(a==-1&&b==-1) break; if(a==0&&b==0) { if(v==0) { printf("Yes\n"); continue; } if(num==len-1) //划重点！！ printf("Yes\n"); else printf("No\n"); num=len=v=0; for(i=0;i<100001;++i) s[i]=false; continue; } v=1; if(s[a]==false) len++;//点数 if(s[b]==false) len++; s[a]=s[b]=true; num++;//边数 } return 0;