小希的迷宫.doc

小希的迷宫 Problem Description 上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。  ? Input 输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。 整个文件以两个-1结尾。 ? Output 对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出Yes，否则输出No。 ? Sample Input 6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1 ? Sample Output Yes Yes No #includeiostream using namespace std; int pre[100010]; int rank[100010];//节点个数 int edge=0,node=0; int find(int i) { int t=i; for(;pre[i]!=-1;i=pre[i]);//找到根节点 /*for(;pre[t]!=-1;t=pre[t])//压缩路径 pre[t]=i;*/ return i; } int Union(int i,int j) { i=find(i); j=find(j); if(i==j)//根节点相同，如果相连便成环 return 0; else { edge++; pre[j]=i; rank[i]+=rank[j]; /*if(rank[i]rank[j]) { pre[j]=i; rank[i]+=rank[j]; } else { pre[i]=j; rank[j]+=rank[i]; } node=(rank[i]rank[j])?rank[i]:rank[j];*/ node=rank[i]; return 1; } } int main() { int n,m,i,tree=1; memset(pre,-1,sizeof(pre)); for(i=0;i100010;i++) pre[i]=-1, rank[i]=1; while(scanf(%d%d,m,n)m!=-1) { if(m+n==0) { if(tree) { if(edge==node-1||(edge+node==0)) printf(Yes\n); else printf(No\n); } for(i=0;i100010;i++) pre[i]=-1, rank[i]=1; tree=1;edge=0;node=0; } else if(tree) { tree=Union(m,n); if(!tree)//找到环 printf(No\n); } } } Myself： #includeiostream using namespace std; #define N 100010 int pre[N];//前导数组 int rank[N];//节点个数 int node=0,edge