类型： 并查集
并查集简述：
定义：
并查集(union-find sets)是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
基本操作：
-
Make_Set(x) 把每一个元素初始化为一个集合：
初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身（也可以根据情况而变）。
-
Find_Set(x) 查找一个元素所在的集合:
查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！这个才是并查集判断和合并的最终依据。判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。
-
Union(x,y) 合并x,y所在的两个集合：
合并两个集合，也是使一个集合的祖先成为另一个集合的祖先。具体过程为，利用Find_Set找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。
-
Find_Set(x)时 路径压缩：
寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find_Set(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？
答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find_Set(x)时复杂度就变成O(1)了。
-
Union(x,y)时 按秩合并：
即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。
例题：
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
题解：
此题是并查集的基本应用。只需要使用并查集判断是否有环路 且 是否只有单个集合。
有坑。。。 输入 0 0 输出Yes
代码：
include <iostream>
include <cstdio>
include <cstring>
using namespace std;
const int MAX = 100005;
int flag = 0,maxx=0;
int vis[MAX],pre[MAX]; // pre用来存index的父节点，路径压缩后存的是根节点。
//vis用来判断是否用到这个点。
void init(){ //初始化
for (int i = 0; i < MAX; ++i)
{
pre[i] = i;
}
memset(vis,0,sizeof(vis));
flag = 0;
maxx=0;
}
int find(int v){ // find操作
int r = v;
while(pre[r] != r){ // 寻到当前状态的根节点
r = pre[r];
}
int i = v,j;
while(i != r){ // 回溯过程 将所有子节点的pre改为父节点。
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}
void join(int v1,int v2){
int newX = find(v1),newY = find(v2);
if(newX == newY && v1 != v2) // 使用并查集判断时候有环路。
{
flag = 1;
}
else
{
pre[newX] = newY; // 吧点加入集合
}
}
void isconnect(){ // 判断是否有只有单个图。
int val = find(pre[maxx]);
for (int i = 0; i < maxx; ++i)
{
if(vis[i] != 0){
if(find(pre[i]) != find(pre[maxx])){
flag = 1;
break;
}
}
}
}
int main()
{
int x,y;
while(scanf("%d%d",&x,&y))
{
init();
if(x==0&&y==0){
printf("Yes\n");
continue;
}
if(x == -1 && y == -1)
break;
vis[x] = 1;
vis[y] = 1;
maxx = max(maxx,max(x,y));
join(x,y);
while(scanf("%d%d",&x,&y) && x && y){
vis[x] = 1;
vis[y] = 1;
maxx = max(maxx,max(x,y));
join(x,y);
}
isconnect();
if(flag)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}