【算法-位元組筆試-中等難度】Tarjan算法求解公共祖先問題LCA，并介紹倍增算法

今天位元組筆試的第二題，詳情由于保密協定不能上網，但是大意就是給一大堆節點，去求LCA。遞歸直接爆棧，用stack寫遞歸有一個點，改進優化了一下有兩個點…… 我印象中這個算法挺簡單的，就搜了一下，果然找到了。不是，現在校招算法題都這麼喪病了嗎。由于保密協定，不能放代碼。後面放Tarjan算法學習筆記。

LCA問題參考資料， Tarjan的時間複雜度為O((n+q)× 并查集的複雜度 )，而使用路徑壓縮和按秩合并的并查集複雜度為O(Alpha(n))。是以作為離線算法，Tarjan比倍增算法快很多。但作為線上算法，倍增算法能實時得到解法。 RMQ

複雜度介紹：

Tarjan的複雜度為O(n+q)
RMQ預處理為O(nlogn)，查詢O(1)
倍增算法複雜度為O((n+q)logn)

參考資料：

Tarjan求解LCA，非常好的教學，很詳細地列舉了LCA的步驟。關鍵是有圖，有逐漸分解的圖，非常好。

僞代碼

Tarjan(u)//marge和find為并查集合并函數和查找函數
{
    for each(u,v)    //通路所有u子節點v
    {
        Tarjan(v);        //繼續往下周遊
        marge(u,v);    //合并v到u上
        标記v被通路過;
    }
    for each(u,e)    //通路所有和u有詢問關系的e
    {
        如果e被通路過;
        u,e的最近公共祖先為find(e);
    }
}

複制

具體實作代碼

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int N = 5;
vector<vector<int> > lib;//假設lib為二維動态數組，lib[i]表示節點i的所有孩子vector
vector<int> parent(N,0);//并查集數組
vector<bool> isVisited(N,false);
vector<vector<int> > query;//query關系，雙向的

int find(int e){
    if(parent[e] != e) return find(parent[e]);
    return e;
}

void Tarjan(int u){
    //通路所有的孩子
    for(int i =0;i<lib[u].size();i++){
        int v = lib[u][i];
        Tarjan(v);
        parent[v] = u;//merge
        isVisited[v] = true;
    }
    for(int i = 0;i<query[u].size();i++){
        int e = query[u][i];
        if(isVisited[e]){
            cout<<"u和e的共同祖先為"<<find(u,e)<<endl;
        }
    }
}

int main(void){
    for(int i = 0;i<N;i++){
        parent[i] = i;
    }
    Tarjan(0);
    cout<<"test"<<endl;
    return 0;
}

複制

倍增算法

參考資料：

b站視訊
csdn

執行個體代碼（有點問題）

#include <cstring>
#include <algorithm>
const int maxn = 1000;//遞歸棧的最大深度，原則上等于點的數量.
const int maxm = 500;
const int maxh = 31;

//定義見前向星
int info[maxn];
int point[maxm];
int next[maxm];

int dep[maxn];//深度數組
int anc[maxn][maxh];
void dfs(int root){
    static int Stack[maxn];
    int top=0;//棧頂指針

    memset(dep,0,sizeof(dep));
    dep[root] = 1;
    for(int i = 0;i<maxh;i++){
        anc[root][i] = root;//根節點無論怎麼跳，都是根節點
    }
    Stack[++top] = root;//Stack[1] = top;
    while(top){
        int x = Stack[top];
        if(x != root){
            for(int i = 1;i<maxh;i++){//按照方程更新數組
                int y = anc[x][i-1];
                anc[x][i] = anc[y][i-1];
            }
        }
        for(int &i = info[x];i;i=next[i]){
            int y = point[i];
            if(y!=anc[x][0]){
                dep[y] = dep[x] + 1;
                anc[y][0] = x;
                Stack[++top] = y;
            }
        }
        while(top && head[Stack[top]] == 0) top--;//清理葉子節點
    }
    void swim(int &x,int H){
        //目标是讓x向上跳H步，使用二進制方式
        for(int i=0;H>0;i++){
            if(H&1) x = anc[x][i];//i相當于現在跳2^i步，當H%2==1時
            x /= 2;//相當于右移
        }
    }
    int lca(int x,int y){
        int i;
        if(dep[x]>dep[y]) swap(x,y);
        swim(y,dep[y]-dep[x]);
        if(x==y) return x;
        for(;;){
            for(i=0;anc[x][i]!=anc[y][i];i++); //同時起跳，尋找不重疊的最近的父節點
            if(i==0){//找不到，則顯然上一個節點即為LCA
                return anc[x][0];
            }
            //起跳，因為anc[x][i] == anc[y][i]，是以隻能跳到i-1
            x = anc[x][i-1];
            y = anc[y][i-1];
        }
        return -1;//有點問題，應該走不到這一步
    }
}

複制

該代碼有一些問題：

為什麼葉子節點在深搜中全部丢棄，這樣它們的anc數組就沒有辦法更新了
最後lca的時候，-1是到不了的，因為上面是死循環，沒有對其進行判斷。

OI wiki的代碼，題目有些差別，不過思想是一樣的

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define MXN 50007
using namespace std;
std::vector<int> v[MXN];//鄰接表寫法
std::vector<int> w[MXN];
//fa表示親緣數組，cost表示每一跳的代價
int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;
void dfs(int root, int fno) {//用顯式DFS做，其實差不多
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}
int lca(int x, int y) {
  if (dep[x] > dep[y]) swap(x, y);
  int tmp = dep[y] - dep[x], ans = 0;
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
  if (y == x) return ans;
  for (int j = 30; j >= 0 && y != x; --j) {
    if (fa[x][j] != fa[y][j]) {
      ans += cost[x][j] + cost[y][j];
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  ans += cost[x][0] + cost[y][0];
  return ans;
}
int main() {
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    scanf("%d %d %d", &a, &b, &c);
    ++a, ++b;
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  dfs(1, 0);
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &a, &b);
    ++a, ++b;
    printf("%d\n", lca(a, b));
  }
  return 0;
}

複制