小希的迷宫

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25010 Accepted Submission(s): 7683

Problem Description 上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。

IDC94c6ytcTV+8r9ttTB0LHto6yx7cq+wcvSu8z1zai1wMGsvdO1xMG9uPa3v7zktcSx4LrFoaO3v7zktcSx4LrF1sHJ2c6qMaOsx9Kyu7Osuf0xMDAwMDCho8O/wb3X6cr9vt3Wrrzk09DSu7j2v9XQ0KGjPGJyPgrV+7j2zsS8/tLUwb249i0xveHOsqGjPGJyPgoKIAo8YnI+Ck91dHB1dAq21NPayuTI67XEw7/Su9fpyv2+3aOsyuSz9r32sPzAqNK70NCho8jnufu4w8PUuay3+7rP0KHPo7XEy7zCt6OsxMfDtMrks/Y="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

这也是一道并查集的题

解题思路：题目意思是找到判断是不是连通无环的图。

1。判断成环：读入过程中，合并集合的时候，如果，当前读入的两个
元素属于同一个集合，那么肯定是No。

2。判断连通：只要判断根节点数为1即可。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           using namespace std; #define f1(i, n) for(int i=0; i
          
           =1; i--) #define f4(i, n) for(int i=1; i
           
            1 || flag==1)//有环或断根节点大于1则是No printf("No\n"); else printf("Yes\n"); } return 0; }

注意：当输入的这组数据只有 0 0 时，依然是满足条件的，即应输出 "Yes"

HDU 1272： 小希的迷宫（并查集）

小希的迷宫

HDU 1272：小希的迷宫（并查集）