求最近公共祖先LCA三种方法

tarjan求lca

• 这种算法本质上是用并查集对向上标记法的优化，是离线算法，即一次性读入所有询问，统一计算，统一输出。
  时间复杂度(O(n+m))

  • v[]进行标记
    (v[x]doteq 0) --> x节点未访问过
    (v[x]doteq 1) --> x节点已经访问，但未回溯
    (v[x]doteq 2) --> x节点已经访问并回溯

• code

  #include <cstdio>
  #include <vector>
  #include <algorithm>
  using namespace std;
  const int N = 1e5+5;
  struct side {
      int t, d, next;
  }e[N<<1];
  int head[N], tot;
  void add(int x, int y, int z) {
      e[++tot].next = head[x];
      head[x] = tot;
      e[tot].t = y, e[tot].d = z;
  }
  int n, m, Q, d[N], f[N], v[N], ans[N];
  vector<int> q[N], h[N];
  int found(int x) {
      return x == f[x] ? x : (f[x] = found(f[x]));
  }
  void Dfs(int x) {
      v[x] = 1;
      for (int i = head[x]; i; i = e[i].next) {
          int y = e[i].t;
          if (v[y]) continue;
          d[y] = d[x] + e[i].d;
          Dfs(y);
          f[y] = x;
      }
      for (int i = 0; i < q[x].size(); i++) {
          int y = q[x][i], id = h[x][i];
          if (v[y] != 2) continue;
          ans[id] = min(ans[id], d[x] + d[y] - 2*d[found(y)]);
      }
      v[x] = 2;
  }
  int main() {
      scanf("%d%d", &n, &m);
      for (int i = 1; i <= n; i++) f[i] = i;
      while (m--) {
          int x, y, z;
          scanf("%d%d%d", &x, &y, &z);
          add(x, y, z); add(y, x, z);
      }
      scanf("%d", &Q);
      for (int i = 1; i <= Q; i++) {
          int x, y;
          scanf("%d%d", &x, &y);
          if (x == y) continue;
          ans[i] = 1 << 30;
          q[x].push_back(y), h[x].push_back(i);
          q[y].push_back(x), h[y].push_back(i);
      }
      Dfs(1);
      for (int i = 1; i <= Q; i++)
          printf("%d
  ", ans[i]);
      return 0;
  }
  

倍增求Lca

• f[x][k]表示从x向根节点走(2^k)步到达的节点
  d[x]表示树的深度
  预处理时间复杂度为(O(nlog n)),每次询问时间复杂度为(O(log n))

  • code

    int d[N], f[N][21];
    void dfs(int x, int fa) {
        f[x][0] = fa;
        d[x] = d[fa] + 1;
        for (int i = 1; i <= 20; i++)
            f[x][i] = f[f[x][i-1]][i-1];
        for (int i = head[x]; i; i = e[i].next) 
            if (e[i].t != fa) dfs(e[i].t, x);
    }
    int found(int x, int l) {
        int a = 0;
        while (l) {
            if (l & 1) x = f[x][a];
            l >>= 1; a++;
        }
        return x;
    }
    int lca(int x, int y) {
        if (d[x] > d[y]) swap(x, y);
        y = found(y, d[y] - d[x]);
        if (x == y) return x;
        for (int i = 20; i >= 0; i--)
            if (f[x][i] != f[y][i])
                x = f[x][i], y = f[y][i];
        return f[x][0];
    }
    

推荐

树链剖分求lca

• 轻重链剖分
  • code

    //树链剖分
    #include <cstdio>
    using namespace std;
    const int N = 5e5+5;
    struct Side {
        int t, next;
    }e[N<<1];
    int head[N], tot;
    void Add(int x, int y) {
        e[++tot] = (Side){y, head[x]};
        head[x] = tot;
    }
    int siz[N], f[N], son[N], d[N], top[N];
    void Dfs1(int x) {
        siz[x] = 1;
        d[x] = d[f[x]] + 1;
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].t;
            if (y == f[x]) continue;
            f[y] = x;
            Dfs1(y);
            siz[x] += siz[y];
            if (!son[x] || siz[son[x]] < siz[y])
                son[x] = y;
        }
    }
    void Dfs2(int x, int tp) {
        top[x] = tp;
        if (!son[x]) return;
        Dfs2(son[x], tp);
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].t;
            if (y == f[x] || y == son[x]) continue;
            Dfs2(y, y);
        }
    }
    int Lca(int x, int y) {
        while (top[x] != top[y])
            d[top[x]] > d[top[y]] ? x = f[top[x]] : y = f[top[y]];
        return d[x] < d[y] ? x : y;
    }
    int n, m, s;
    int main() {
        scanf("%d%d%d", &n, &m, &s);
        for (int i = 1; i < n; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            Add(x, y); Add(y, x);
        }
        Dfs1(s); Dfs2(s, s);
        while (m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d
    ", Lca(x, y));
        }
        return 0;
    }