题意分析

将每个 $n -$ 交点当作一个节点，相邻$n -$ 交点之间的路径看作边，利用并查集来判断起始 $n -$交点和结束 $n -$ 交点是否处于同一个集合中。若处于同一集合，就意味着它们之间存在路径相连，能够从起始点抵达结束点；反之则不能。

解题思路

运用 $read$ 函数读取输入，将 $n$ 维坐标转换为一个长整型数，从而简化存储和处理。 当输入为$-1$ 时，表明当前迷宫的路径信息读取完毕。 利用 $memset(fa, -1, sizeof(fa))$ 对并查集数组$fa$ 进行初始化，把每个元素的父节点设为$-1$，表示每个元素初始时都属于一个独立的集合。 借助 $map<long long, int> mp$ 把每个$n -$ 交点的坐标映射为一个唯一的整数编号，以此缩小数据范围，方便并查集的操作。读取每一条路径的两个端点，若这两个端点还未被编号，就为其分配一个新的编号。 利用 $find$函数查找这两个端点所属的集合，若它们不属于同一个集合，就使用 $fa[find(mp[a])] = find(mp[b])$ 将这两个集合合并。 起始 n - 交点和结束 n - 交点分别被编号为$1$ 和 $2$。 若 $find(1) == find(2)$，则说明起始点和结束点处于同一个集合中，能够从起始点到达结束点；反之则不能。

C++实现

cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
//英语         看博友分析       抄博友程序       并查集      map缩小数据范围       背 
int n;
long long read()
{
	long long a;
	scanf("%lld",&a);
	if(a==-1)
	{
		//cout<<"hi"<<endl;
		return -1;
	}
	for(int i=1;i<n;i++)
	{
		int t;
		scanf("%d",&t);
		a=a*10+t;
	}
	return a;
}
int fa[20000];
int find(int x)
{
	if(fa[x]==-1)//
	{
		return x;
	}else
	{
		return fa[x]=find(fa[x]);
	}
}
int main()
{
	int tag=0;
	while(1)
	{
		tag++;
		scanf("%d",&n);
		if(n==0)
		{
			break;
		}
		memset(fa,-1,sizeof(fa));
		map<long long,int> mp;
		mp.clear();
		int zhi=1;
		long long a=read();
		//cout<<a<<endl;		
		if(mp[a]==0)
		mp[a]=zhi++;
		long long b=read();
		//cout<<b<<endl;
		if(mp[b]==0)
		mp[b]=zhi++;		
		while(1)
		{
			long long a=read();
			//cout<<a<<endl;
			if(mp[a]==0)
			mp[a]=zhi++;
			if(a==-1)
			{
				break;
			}
			long long b=read();
			//cout<<b<<endl;
			if(mp[b]==0)
			mp[b]=zhi++;
			//cout<<find(mp[a])<<endl;
			//cout<<find(mp[b])<<endl;
			if(find(mp[a])!=find(mp[b]))
			{
				fa[find(mp[a])]=find(mp[b]);
			}
		}
		if(find(1)==find(2))
		{
			cout<<"Maze #"<<tag<<" can be travelled"<<endl;
		}else
		{
			cout<<"Maze #"<<tag<<" cannot be travelled"<<endl;
		}	
	}
	return 0;
}

分析：

算法思想 并查集是一种用于处理不相交集合的合并与查询问题的数据结构。其核心操作包含两个：

查找（Find）：查找元素所属的集合，即找到元素所在集合的代表元素。

合并（Union）：把两个不相交的集合合并成一个集合。

在本题里，将每个 n - 交点当作一个节点，相邻 n - 交点之间的路径看作边，利用并查集来判断起始 n - 交点和结束 n - 交点是否处于同一个集合中。若处于同一集合，就意味着它们之间存在路径相连，能够从起始点抵达结束点；反之则不能。

实现步骤：

1.输入处理：

运用 read 函数读取输入，将 n 维坐标转换为一个长整型数，从而简化存储和处理。 当输入为 -1 时，表明当前迷宫的路径信息读取完毕。

2.并查集初始化：

利用 memset(fa, -1, sizeof(fa)) 对并查集数组 fa 进行初始化，把每个元素的父节点设为 -1，表示每个元素初始时都属于一个独立的集合。

3.节点编号映射：

借助 map<long long, int> mp 把每个 n - 交点的坐标映射为一个唯一的整数编号，以此缩小数据范围，方便并查集的操作。

4.路径合并：

读取每一条路径的两个端点，若这两个端点还未被编号，就为其分配一个新的编号。

利用 find 函数查找这两个端点所属的集合，若它们不属于同一个集合，就使用 fa[find(mp[a])] = find(mp[b]) 将这两个集合合并。

5.判断可达性： 起始 n - 交点和结束 n - 交点分别被编号为 1 和 2。

若 find(1) == find(2)，则说明起始点和结束点处于同一个集合中，能够从起始点到达结束点；反之则不能。

C++实现：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int n;
long long read()
{
	long long a;
	scanf("%lld",&a);
	if(a==-1)
	{
		//cout<<"hi"<<endl;
		return -1;
	}
	for(int i=1;i<n;i++)
	{
		int t;
		scanf("%d",&t);
		a=a*10+t;
	}
	return a;
}
int fa[20000];
int find(int x)
{
	if(fa[x]==-1)//
	{
		return x;
	}else
	{
		return fa[x]=find(fa[x]);
	}
}
int main()
{
	int tag=0;
	while(1)
	{
		tag++;
		scanf("%d",&n);
		if(n==0)
		{
			break;
		}
		memset(fa,-1,sizeof(fa));
		map<long long,int> mp;
		mp.clear();
		int zhi=1;
		long long a=read();
		//cout<<a<<endl;		
		if(mp[a]==0)
		mp[a]=zhi++;
		long long b=read();
		//cout<<b<<endl;
		if(mp[b]==0)
		mp[b]=zhi++;		
		while(1)
		{
			long long a=read();
			//cout<<a<<endl;
			if(mp[a]==0)
			mp[a]=zhi++;
			if(a==-1)
			{
				break;
			}
			long long b=read();
			//cout<<b<<endl;
			if(mp[b]==0)
			mp[b]=zhi++;
			//cout<<find(mp[a])<<endl;
			//cout<<find(mp[b])<<endl;
			if(find(mp[a])!=find(mp[b]))
			{
				fa[find(mp[a])]=find(mp[b]);
			}
		}
		if(find(1)==find(2))
		{
			cout<<"Maze #"<<tag<<" can be travelled"<<endl;
		}else
		{
			cout<<"Maze #"<<tag<<" cannot be travelled"<<endl;
		}	
	}
	return 0;
}