题干

根据海绵城市建设指挥部要求，怡山小学将对校内道路进行改造，铺设透水砖。这样有些道路将不能通行。为了不妨碍假期少先队的校内活动安排，大队宣传委员小黄需要知道一些关键的活动地点是否可以到达。

已知校内一共有20处建筑，分别标为1号楼，２号楼，......，２０号楼。有些楼之间有道路连接，道路是双向的，如果Ａ楼与Ｂ楼间有道路，那么既可以从Ａ楼到Ｂ楼，也可以从Ｂ楼到Ａ楼。

首先将输入校内的道路数n, 接下来分n行输入各条道路的信息，每行有两个整数（均在１和２０之间），代表这两座楼之间有道路连接。　接下来输入查询数m, 然后分m行输入要查询的楼间连路信息，每行有两个整数（均在１和２０之间）。

如果两楼之间可以通过一条路径到达（中途有可能经过其它楼），则输出两楼是连接的，否则输出两楼是断开的。

函数接口定义

完成查询两建筑是否连通的函数test

主函数

using namespace std;
const int N=21;

/* 请在这里填写答案 */

int main()
{
  int a[N][N]={0}, n, m, i, j, k;
  cin>>n;
  for(i=0;i<n;i++){
    cin>>j>>k;
    a[j][k]=a[k][j]=1;
  }
  cin>>m;
  for(i=0;i<m;i++){
    cin>>j>>k;
    cout<<j<<'-'<<k<<' ';
    if(test(a, j, k)) cout<<"connected"<<endl; else cout<<"disconnected"<<endl;
  }    
  return 0;
}

输入

2
1 2
2 3
2
1 3
1 4

输出

1-3 connected
1-4 disconnected

解答

bool test(int a[N][N], int j, int k)//找到一条从j到k的通路，若不存在则返回false
{
	//维护一个一维数组，模拟栈的操作，从j开始深搜到一个邻居i且没有搜索过，则将i入栈，如果i==k则搜索成功 
	//维护一个一维数组，有N个元素，用于记录某个楼是否搜索过 
	int stack[N+1] = {0}; //存储从j开始走过的路径，如 j m n t，表示从j开始经过m n走到了t 
	bool visited[N+1] = {false};
	int top = 0; //top记录数组stack的最后一个元素的位置， 
	//首先j入栈
	stack[++top] = j;
	visited[j] = true;
	while(top > 0) //当前栈不空
	{
		int cur = stack[top--]; //得到当前栈顶
		//把与cur连接的所有未访问过的楼号压入栈
		for(int i = 0; i < N; i++)
		{
			if(a[cur][i] == 1 && visited[i] == false)
			{
				stack[++top] = i;
				if(i == k) return true; //访问到k则表示从j到k有通路
				visited[i] = true;
			} 
		}
	}
	return false;
}