小希的迷宫

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 129 Accepted Submission(s) : 51

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

这题思路非常简单。但是wa了无数遍。
注意3点。
1.必须是联通的，也就说最后返回的跟必须是释怀一个
2. 发现 2点已经连通 时。就说明已经有路可以走了。不满足
3.0 0 这组数据 输出yes。（看了别人的才发现）。

 1 #include<string.h>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 int par[1000000];
 6 int vis[100006];
 7 int flag;
 8 int findi(int x)
 9 {
10 while(par[x]!=x)
11 x=par[x];
12 return x;
13 }
14 void unioni(int x,int y)
15 {
16 
17 int xx=findi(x);
18 int yy=findi(y);
19 if(xx!=yy)
20 par[xx]=yy;
21 else if(xx==yy)
22 flag=0;
23 }
24 
25 int main()
26 {
27 int n,m;
28 while(1)
29 {
30 cin>>n>>m;
31 
32 if(n==-1&&m==-1)
33 break;
34 if(n==0&&m==0)
35 {
36 cout<<"Yes"<<endl;
37 continue;
38 }
39 for(int i=1;i<100005;i++)
40 par[i]=i;
41 memset(vis ,0,sizeof vis);
42 
43 flag=1;
44 vis[n]=1;
45 vis[m]=1;
46 unioni(n,m);
47 int q,w;
48 while(cin>>q>>w)
49 {
50 if(q==0&&w==0)
51 break;
52 vis[q]=1;
53 vis[w]=1;
54 unioni(q,w);
55 
56 }
57 int ppp=0;
58 for(int i=1;i<100005;i++)
59 {
60 if(vis[i]==1&&par[i]==i)
61 ppp++;
62 }
63 if(flag==0||ppp!=1)
64 cout<<"No"<<endl;
65 if(flag==1&&ppp==1)
66 cout<<"Yes"<<endl;
67 }
68 return 0;
69 }