NC19814（最短路 ）

感受

思路






复杂度分析

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
const int maxm = 200000 + 500;
struct edge{
    int v, nex;
}e[maxm];
int head[maxn], cnt, n, m, fa[maxn];
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    for(int i = 1; i <= n; i++){
        head[i] = -1; fa[i] = i;
    }
}
int find_fa(int x){
    return x == fa[x] ? x : fa[x] = find_fa(fa[x]);
}
void join(int x, int y){
    x = find_fa(x); y = find_fa(y);
    if(x != y) fa[x] = y;
}
bool same(int x, int y){
    return find_fa(x) == find_fa(y);
}
struct node{
    int u, v;
}res[200];
int tot;
int ff[maxn][25], dep[maxn];
void dfs(int u, int f, int d){
    dep[u] = d;
    ff[u][0] = f;
    for(int i = 1; i <= 17; i++){
        ff[u][i] = ff[ff[u][i - 1]][i - 1];
    }
    int v;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == f) continue;
        dfs(v, u, d + 1);
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int d = dep[u] - dep[v], i = 0; d; d >>= 1, i++){
        if(d & 1) u = ff[u][i];
    }
    if(u == v) return u;
    for(int i = 17; i >= 0; i--){
        if(ff[u][i] != ff[v][i]){
            u = ff[u][i];
            v = ff[v][i];
        }
    }
    return ff[u][0];
}
node query[maxn]; int q;
int ans[maxn], dis[maxn], vis1[maxn];
bool vis[maxn];
void bfs(int s){
    for(int i = 1; i <= n; i++){
        vis1[i] = false;
    }
    dis[s] = 0;
    queue<int> que; que.push(s); vis1[s] = true;
    while(!que.empty()){
        int u = que.front(), v; que.pop();
        for(int i = head[u]; ~i; i = e[i].nex){
            v = e[i].v;
            if(vis1[v]) continue;
            que.push(v); vis1[v] = true; dis[v] = dis[u] + 1;
        }
    }
    for(int i = 1; i <= q; i++){
        ans[i] = min(ans[i], dis[query[i].u] + dis[query[i].v]);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    init();
    int u, v;
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &u, &v);
        if(same(u, v)){
            res[++tot] = (node){u, v};
        }
        else{
            join(u, v); add_edge(u, v); add_edge(v, u);
        }
    }
    dfs(1, 0, 1);
    scanf("%d", &q);
    for(int i = 1; i <= q; i++){
        scanf("%d%d", &u, &v);
        query[i] = (node){u, v};
        ans[i] = dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    for(int i = 1; i <= tot; i++){
        add_edge(res[i].u, res[i].v); add_edge(res[i].v, res[i].u);
    }
    for(int i = 1; i <= tot; i++){
        u = res[i].u; v = res[i].v;
        if(!vis[u]){
            bfs(u);
            vis[u] = true;
        }
        if(!vis[v]){
            bfs(v);
            vis[v] = true;
        }
    }
    for(int i = 1; i <= q; i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}