HDU 2874：LCA轉RMQ結合並查集解決不連通圖的最短路徑查詢

題目大意

給定一個可能不連通的無向加權圖，需回答多組查詢：若兩城市不連通輸出"Not connected"，否則輸出兩點間的最短距離。節點數N≤10000，邊數M未指定但隱含較大。

解題策略

1. 並查集判斷連通性：預處理所有邊，構建並查集，查詢時O(α(N))判斷兩點是否同屬一連通塊。
2. 虛擬根節點統一處理森林：對每個連通塊的根節點（並查集代表元），連接一條權重為0的邊到虛擬節點0，將森林轉為單棵樹。
3. LCA轉RMQ求最短路徑：在虛擬樹上DFS記錄歐拉序列、深度、首次出現位置及根節點距離dis[]。利用ST表預處理RMQ，查詢LCA後按公式dis[u] + dis[v] - 2*dis[lca]計算距離。

關鍵技術細節

• DFS時同步構建Euler序列E[]、深度L[]、首次出現H[]，以及距離前綴和dis[]。
• RMQ預處理dp[i][j]存儲區間最小深度對應的Euler序列索引，查詢時取深度較小者。
• 虛擬節點0的深度設為1，確保所有原始節點深度≥2，避免邊界錯誤。
• 多測試用例循環讀取直到EOF，每輪需清空圖、重置陣列。

代碼骨架 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
struct Edge { int to, cost; };
vector<Edge> G[MAXN];
int dp[MAXN*2][20], L[MAXN*2], E[MAXN*2], H[MAXN], dis[MAXN];
bool vis[MAXN];
int fa[MAXN], n, k, T;

int find_set(int x) { return fa[x]==x ? x : fa[x]=find_set(fa[x]); }
void unite(int a, int b) { fa[find_set(a)] = find_set(b); }

void dfs(int u, int dep) {
    vis[u] = true;
    E[++k] = u; L[k] = dep; H[u] = k;
    for (auto &e : G[u]) if (!vis[e.to]) {
        dis[e.to] = dis[u] + e.cost;
        dfs(e.to, dep+1);
        E[++k] = u; L[k] = dep;
    }
}

void rmq_init(int len) {
    for (int i=1; i<=len; ++i) dp[i][0] = i;
    for (int j=1; (1<<j)<=len; ++j)
        for (int i=1; i+(1<<j)-1<=len; ++i)
            dp[i][j] = (L[dp[i][j-1]] < L[dp[i+(1<<(j-1))][j-1]]) ? dp[i][j-1] : dp[i+(1<<(j-1))][j-1];
}

int lca(int u, int v) {
    u = H[u]; v = H[v];
    if (u > v) swap(u, v);
    int k = 31 - __builtin_clz(v - u + 1);
    return (L[dp[u][k]] < L[dp[v-(1<<k)+1][k]]) ? E[dp[u][k]] : E[dp[v-(1<<k)+1][k]];
}

int main() {
    int m, a, b, c;
    while (scanf("%d%d%d", &n, &m, &T) == 3) {
        // 初始化
        for (int i=0; i<=n; ++i) fa[i]=i, G[i].clear();
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        // 讀邊、建圖、合併並查集
        for (int i=0; i

總結
本題巧妙結合並查集與LCA+RMQ，將不連通圖轉化為單樹問題，實現高效距離查詢。核心在於虛擬節點的引入與ST表的正確構建。