P2307 迷宫
题目背景
无
题目描述
小希非常喜欢玩迷宫游戏，现在她自己设计了一个迷宫游戏。在她设计的迷宫中，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间 A 和 B，那么既可以通过它从房间 A 走到房间 B，也可以通过它从房间 B 走到房间 A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从555到达888。
输入格式
输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为111，且不超过100000100000100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。
输出格式
对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出1，否则输出0。
输入输出样例 #1
输入 #1
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输出 #1
1 1 0说明/提示
无
C++实现
#include<cstdio>#include<cstring>intf[100001]/*祖先*/,a,b,sum/*集合数量*/;boolbook[100001]/*是否出现*/,flag/*是否违规*/;voidcls(){//初始化for(registerinti=1;i<=100000;i++)f[i]=i;memset(book,0,sizeof(book));sum=0;flag=false;}intfind(intx){//路径压缩般找祖先if(f[x]==x)returnx;returnf[x]=find(f[x]);}intmain(){cls();while(scanf("%d%d",&a,&b)==2)//疯狂输入{if(a==-1&&b==-1)break;if(a==0&&b==0){printf("%c\n",((!flag&&sum==1)?'1':'0'));cls();continue;}//这组数据结束if(!book[a])sum++;//集合增加if(!book[b])sum++;//集合增加book[a]=true;book[b]=true;//标记intx1=find(a),x2=find(b);//祖先if(x1==x2)flag=true;//标记else{sum--;f[x1]=x2;}//修改}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
