本文共 1636 字，大约阅读时间需要 5 分钟。

原题链接：

一：原题内容

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

6 8  5 3  5 2  6 45 6  0 08 1  7 3  6 2  8 9  7 57 4  7 8  7 6  0 03 8  6 8  6 45 3  5 6  5 2  0 0-1 -1

YesYesNo

二：分析理解

1.检测是否存在环，如果存在，则输出No

2.检测是否连通，连通就是任意两点可达，如果不连通，也就是存在大于1的rootNum，输出No

三：AC代码

#include
   
        #include
    
       #include
     
        using namespace std;int pre[100001];int vis[100001];bool flag;//标记是否存在环int rootNum;//标记源点个数，检测是否连通int x, y;int Find(int x){	return (x != pre[x]) ? Find(pre[x]) : x;}void Union(int x, int y){	int x_root = Find(x);	int y_root = Find(y);	if (x_root != y_root)		pre[y_root] = x_root;	else		flag = 0;//为环}int main(){	while (scanf("%d%d", &x, &y))	{		if (x == -1 && y == -1)			break;		if (x == 0 && y == 0)//这点挺坑的，容易忘记！！！		{			printf("Yes\n");			continue;		}		memset(vis, 0, sizeof(vis));		for (int i = 1; i < 100001; i++)			pre[i] = i;		flag = 1;		rootNum = 0;		vis[x] = vis[y] = 1;		Union(x, y);		while (scanf("%d%d", &x, &y) && (x || y))		{			vis[x] = vis[y] = 1;			Union(x, y);		}		for (int i = 1; i < 100001; i++)		{			if (vis[i])			{				if (i == pre[i])					rootNum++;				if (rootNum >= 2 || flag == false)					break;			}		}		if (rootNum == 1 && flag)			printf("Yes\n");		else			printf("No\n");	}	return 0;}
     
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51063804 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！