牛客國慶集訓派對Day6 最短路 （最小生成樹 + lca + bfs）

題目連結：點此跳轉

題目大意：給一個連通圖，每次詢問兩點間最短路。每條邊的長度都是1。

第一行兩個整數n和m，表示圖的點數和邊數（1≤ n≤ 100000, 1≤ m≤ n+100）。

解題思路：

因為這道題邊的範圍比較特別，1≤m≤n+100。我們先假設m恰好是n-1即圖為一棵樹，那麼我們可以通過最近公共祖先求得兩點的最近距離為dep[a]+dep[b]-2*dep[lca(a,b)]。現在又多出來100條邊，我們要怎麼處理呢？
答案是：bfs 直接對這些邊的一個端點開始暴力搜尋最短路即可。

Code：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+5;

int dp[N][25],f[N],dep[N],dis[120][N],head[N];
int tot,num;
vector<pii> ve;
struct node{
	int now,to,net;
}s[N*2+100];

void add(int u,int v){                           //鏈式前向星存圖
	s[++tot]={u,v,head[u]};
	head[u]=tot;
	s[++tot]={v,u,head[v]};
	head[v]=tot;
}

int find(int x){                         //最小生成樹
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}

void dfs(int node,int fa){                   
	dep[node]=dep[fa]+1;
	dp[node][0]=fa;
	for(int i=1;(1<<i)<=dep[node];i++){
		dp[node][i]=dp[dp[node][i-1]][i-1];
	}
	for(int i=head[node];~i;i=s[i].net){
		if(s[i].to==fa) continue;
		dfs(s[i].to,node);
	}
}

int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int tep=dep[x]-dep[y];
	for(int j=0;tep;j++){
		if(tep&1) x=dp[x][j];
		tep>>=1;
	}
	if(x==y) return x;
	for(int j=21;j>=0&&x!=y;--j){
		if(dp[x][j]!=dp[y][j]){
			x=dp[x][j];
			y=dp[y][j];
		}
	}
	return dp[x][0];
}

void bfs(int node){              
	num++;
	dis[num][node]=0;
	queue<int> q;
	q.push(node);
	while(!q.empty()){
		int star=q.front(); q.pop();
		for(int i=head[star];~i;i=s[i].net){
			if(dis[num][s[i].to]>dis[num][star]+1){
				dis[num][s[i].to]=dis[num][star]+1;
				q.push(s[i].to);
			}
		}
	}
}


int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    memset(dis,0x3f3f,sizeof dis);
    for(int i=1;i<=n;i++){
    	head[i]=-1;
    	f[i]=i;
	}
	
    for(int i=0;i<m;i++){
    	int u,v;
    	scanf("%d%d",&u,&v);
    	if(find(u)==find(v)) ve.push_back({u,v});
    	else{
    		f[find(u)]=find(v);
    		add(u,v);
		}
	}
    dfs(1,0);                // lca 預處理
    
    for(auto k:ve){                    
    	add(k.first,k.second);
	}
	for(auto k:ve){                  //求這個點到其他點的最短距離
		bfs(k.first);
	}
	
	int q;
	scanf("%d",&q);
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		int ans=dep[a]+dep[b]-2*dep[lca(a,b)];
		for(int i=1;i<=num;i++){
			ans=min(ans,dis[i][a]+dis[i][b]);
		}
		printf("%d\n",ans);
	}
	
    
    return 0;
}