***************************************转载请注明出处：http://blog.csdn.net/lttree***************************************

小希的迷宫

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

Yes
Yes
No

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1272

汉语题目，不多说。

并查集来解决，判断要合并的两个集合原来是否属于同一集合。

但是，还有几点要注意：

1. 不止要判断原来是否属于同一集合，还要判断是否有孤立的点。

2.如果没有数据，直接输入0 0，应该输出Yes

3.所有的点并不是连续的，根据例1 可以知道，最小的点是2，最大的点是8，但是没有7这个点。

恩，注意上述几点，就可以完成了。

/*******************************************  
********************************************  
*           Author:Tree                    *  
*    From :  blog.csdn.net/lttree          *  
*      Title : 小希的迷宫                  *  
*    Source: hdu 1272                      *  
*      Hint :  并查集                      *  
********************************************  
*******************************************/    

#include 
  
   
#include 
   
     int father[100010]; bool isright,vis[100010]; void Init( void ) { for( int i=1;i<100010;++i ) father[i]=i; } int Find( int x ) { while( x!=father[x] ) { x=father[x]; } return x; } // 合并函数 void Combine(int a,int b) { int temp_a,temp_b; temp_a=Find(a); temp_b=Find(b); if( temp_a!=temp_b ) father[temp_a]=temp_b; else isright=false; // 如果本来属于同一集合，不属于小希迷宫 } // 判断 是否只有一个集合 bool judge( int Min,int Max ) { int i,js=0; for( i=Min;i<=Max;++i ) if( vis[i] && father[i]==i ) ++js; if( js==1 ) return true; return false; } int main() { int a,b,Max,Min; // 初始化 Init(); isright=true; Min=0x3f3f3f3f; Max=-1; memset(vis,0,sizeof(vis)); while( scanf("%d%d",&a,&b) && (a!=-1||b!=-1) ) { if( !a || !b ) { if( isright ) { // Max!=-1 必须有，防止上来就输入0 0 if( judge(Min,Max)==0 && Max!=-1 ) printf("No\n"); else printf("Yes\n"); } else printf("No\n"); // 完成一组数据，初始化一下 Init(); isright=true; Max=-1; Min=0x3f3f3f3f; memset(vis,0,sizeof(vis)); continue; } //记录哪些点存在 vis[a]=vis[b]=1; // 找最小值与最大值 Max=a>Max?a:Max; Max=b>Max?b:Max; Min=a