• D - Add One Edge
  • 法一：dijkstra
  • 法二：BFS+队列

D - Add One Edge

题意：
给你一个无向图图，分为两个连通块，一个顶点数为 n1(1~n1)，一个顶点数为 n2(n1+1~n1+n2)，图中共有 m 条边。如果现在在两个连通块之间连接一条边，那么顶点 1 与顶点 n1+n2 则相互可达，且对于此种连法，两顶点之间存在一条最短的可达路径。问你在所有的情况中，最短路径的最大值是多少？
思路：

法一：dijkstra

因为问的是最短距离的最大，所以我们首先需要每一个连通块内两顶点到所有点的最短距离，又需要最大的最短距离，所以两个连通块内的最大距离之和+1即为最终答案。
首先利用 dij 处理顶点 1 和顶点 n1+n2 的单源最短路，设顶点 1 所在的连通块与顶点 1 的最远距离为 ans1，顶点 n1+n2 所在的连通块与顶点 n1+n2 的最远距离为ans2，最终的答案即为\(1+ans_1+ans_2\)
注意一点，就是\(0\le n_1+n_2\le 3e5\)，注意全局变量的空间大小！

const int maxm=3e5+5,inf=0x3f3f3f3f,mod=998244353;
int n1,n2,m,ans[2];
vector<int> e[maxm],dis(maxm,inf);
vector<int> vis(maxm,false);

void dij(int x,int p){
	priority_queue<pii,vector<pii>,greater<pii>> q;
	q.push({0,x});
	pii t;
	while(!q.empty()){
		t=q.top();
		q.pop();
		if(vis[t.second]) continue;
		dis[t.second]=t.first;
		ans[p]=max(ans[p],t.first);
		vis[t.second]=true;
		for(auto a:e[t.second]){
			if(!vis[a] && dis[a]>t.first+1){
				q.push({t.first+1,a});
			}
		}
	}
	return ;
}

void solve(){
	cin>>n1>>n2>>m;
	int a,b;
	for(int i=0;i<m;++i){
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dij(1,0);
	dij(n1+n2,1);
	cout<<ans[0]+ans[1]+1<<'\n';
	return ;
}

法二：BFS+队列

其实bfs基本思想与dij相同，利用BFS+队列逐层遍历

const int maxm=3e5+5,inf=0x3f3f3f3f,mod=998244353;
int n1,n2,m,ans[2];
vector<int> e[maxm],dis(maxm,inf);
vector<bool> vis(maxm,false);

void bfs(int x,int p){
	dis[x]=0;
	queue<int> q;
	q.push(x);
	int t;
	while(!q.empty()){
		t=q.front();
		q.pop();
		vis[t]=true;
		for(auto a:e[t]){
			if(!vis[a] && dis[a]>dis[t]+1){
				dis[a]=dis[t]+1;
				ans[p]=max(ans[p],dis[t]+1);
				q.push(a);
			}
		}
	}
	return ;
}

void solve(){
	cin>>n1>>n2>>m;
	int a,b;
	for(int i=0;i<m;++i){
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	bfs(1,0);
	bfs(n1+n2,1);
	cout<<ans[0]+ans[1]+1<<'\n';
	return ;
}