上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。
![M - 小希的迷宫 并查集-LMLPHP]( "M - 小希的迷宫 并查集-LMLPHP")
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
一开始的思路，用set记录超时了，这是一开始的解法
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<iomanip>
#include<iostream>
using namespace std;
#define MAXN 100008
#define INF 0x3f3f3f3f
typedef long long LL;
/*
当试图加入的两个元素在同一并查集，有多条路
*/
int pre[MAXN];
set<int> s;
int find(int x)
{
if(pre[x]==-)
return x;
return pre[x] = find(pre[x]);
}
bool mix(int x,int y)
{
int fx = find(x),fy=find(y);
if(fx==fy)
return false;
pre[fy] = fx;
return true;
}
int main()
{
int x,y;
bool f=false;
memset(pre,-,sizeof(pre));
while(scanf("%d%d",&x,&y))
{
if(x==-&&y==-)
break;
if(x==&&y==)
{
if(!f)
{
set<int>::iterator it = s.begin();
int tmp = find(*it);
it++;
for(it;it!=s.end();it++)
{
if(find(*it)!=tmp)
{
f = true;
break;
}
}
}
if(f) cout<<"No\n";
else cout<<"Yes\n";
memset(pre,-,sizeof(pre));
s.clear();
f = false;
continue;
}
s.insert(x);
s.insert(y);
if(!mix(x,y))
f = true;
}
return ;
}
后来发现可以用数组记录出现过的数字，然后遍历所有数字，如果其中出现两个不同的pre[i]那么说明图不联通，冲突判断用并查集权值判断
#include<stdio.h>
#include<string.h> const int MAXN=;
int F[MAXN];//存储树根
int t[MAXN];//把出现的数都存入这个数组
int q[MAXN];//标记有没有出现过的数 int find(int x)//查找树根
{
if(F[x]==) return x;
return F[x]=find(F[x]);
} int main()
{
int cnt;
int a,b;
bool flag;
while(scanf("%d%d",&a,&b))
{
if(a==-&&b==-) break; //这个一定要加上去。。。。否则 WR了
if(a==&&b==)
{
printf("Yes\n");
continue;
} memset(F,,sizeof(F));
memset(q,,sizeof(q));
cnt=;
F[a]=b;
if(q[a]==)
{
q[a]=;
t[cnt++]=a;
}
if(q[b]==)
{
q[b]=;
t[cnt++]=b;
} flag=true;
while(scanf("%d%d",&a,&b))
{
if(a==&&b==) break; if(flag==false)continue; int t1=find(a);
int t2=find(b);
if(t1==t2)
{
flag=false;
continue;
}
else F[t1]=t2;
if(q[a]==)
{
q[a]=;
t[cnt++]=a;
}
if(q[b]==)
{
q[b]=;
t[cnt++]=b;
}
}
if(flag)
{
int temp=;
for(int i=;i<cnt;i++)
{
if(F[t[i]]==) temp++;
}
if(temp>) flag=false; }
if(flag) printf("Yes\n");
else printf("No\n");
}
return ; }