狡兔 k 窟-bfs

解题思路:

要求两个点之间的最点距离，同时属于同一个洞窟的点他们之间的距离为0

那么该问题可以转换为求解两个洞窟的最短距离

依次构建的图是关于洞窟的而不是点

例如1 3 2 1 2 3：1和4点都属于1号洞窟那么他们两点邻接的其他点，也就等价于1号洞窟邻接了其他洞窟

从而构建洞窟的邻接表

然后通过bfs去求解两个洞窟之间的最小深度

bfs深度依次递增的，因此只要达到了终点洞窟此时的深度就是最小的深度

没必要再继续深度遍历

参考代码:

#include <bits/stdc++.h>
using namespace std;

int n,m;
vector<int> a;//a[i]表示i所属于的洞窟编号 
vector<int> b[5005];//存储洞窟之间的图 

//通过bfs得到两个洞窟之间最近的距离 
int solve(int x,int y){
	if(x == y) return 0;
	queue<int> q;
	q.push(x);
	vector<int> depth(5005,0);//记录该洞窟编号到x的深度，即距离 
	vector<int> vis(5005,0);//标记访问避免重复访问 
	vis[x] = 1;
	//bfs遍历 
	while(!q.empty()){
		int t = q.front();
		q.pop();
		for(int u : b[t]){
			if(u == y) {
				//达到目的点，直接返回，通过bfs遍历 深度是从小到大
				//因此第一次到达目的点就一定是最小的深度 
				return depth[t] + 1;
			}
			else {
				//已经入队了就跳过 
				if(vis[u]) continue;
				//入队 
				q.push(u);
				//标记入队 
				vis[u] = 1;
				//该点到x的深度是x到t的深度 + t到x深度（t是x的邻接点，故深度为1） 
				depth[u] = depth[t] + 1;
			}
		}
	}
}

int main() {
	cin>>n>>m;
	a.resize(n + 1,0);
	for(int i = 1;i <= n;i++){
		cin>>a[i];
	}
	for(int i = 0;i < n-1;i++){
		int x,y;
		cin>>x>>y;
		//构造的是洞窟图，例如1，3是1号洞窟，2，4，5是2号洞窟
		//那么就构造1号洞窟和2号洞窟的关系
		//1，3是1号洞窟，他们能到达的洞窟 合并起来就是1号洞窟能到达其他洞窟的情况 
		//这里还可以先进行去重处理，避免洞窟的邻接点有重复
		if(a[x] != a[y]){//同一个洞窟的没必要再加入图结构
			b[a[x]].push_back(a[y]);
			b[a[y]].push_back(a[x]);
		}
	}
	
	for(int i =0;i<m;i++){
		int x,y;
		cin>>x>>y;
		//输出所求 其实就是这两点所属洞窟的最小深度（距离） 
		cout<<solve(a[x],a[y])<<endl;
	}
    return 0;
}