【图论】最近公共祖先(LCA)

最近公共祖先(LCA)

概念

• 祖先：从某个节点上溯到根节点的所有节点都是该节点的祖先，如图中节点5的祖先为节点3 1 0

• 公共祖先：两个节点共有的祖先，如图中节点2和节点5的公共祖先为1 0

• 最近公共祖先：所有公共祖先中深度最深的祖先，若待求的一个节点本身是另一个节点的祖先，则该节点即为所求最近公共祖先

  

  LCA

朴素算法

思路：将两节点跳至同一深度，让两节点同时上跳至同一节点

方法：DFS

倍增LCA

使用倍增思想，以及st表来寻找祖先。

由倍增思想，我们可以得到某节点\(2^i\)级祖先是\(2^{i-1}\)级祖先的\(2^{i-1}\)级祖先

故我们只需要每次寻找两节点尽可能相遇的位置，则它们的父节点一定相遇，此时父节点便为LCA

具体来说，同时往上走的时候要保证各自到达的节点不同，走到最后在往上走一步即可

时间复杂度\(O(\log n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
int n, m, s;
int st[N][20];
int head[N],depth[N];
int power, cnt;
struct node2{
  int u, f ,e;
};
struct node{
  int to, nxt;
}edge[2*N]; // 无向图 开两倍
// 链式前向星建图
void add_edge(int from, int to){
  edge[++cnt].to = to;
  edge[cnt].nxt = head[from];
  head[from]=cnt;
}
// 非递归版本 防止爆栈
void dfs_stack(int i, int fat){
  stack<node2> stk;
  stk.push({i,0,-1});
  while(!stk.empty()){
    node2 cur = stk.top();
    stk.pop();
    if (cur.e==-1){
      depth[cur.u] = depth[cur.f]+1;
      st[cur.u][0]=cur.f;
      for (int s=1;(1<<s)<=depth[cur.u];s++){
        st[cur.u][s] = st[st[cur.u][s-1]][s-1];
      }
      cur.e = head[cur.u];
    }
    else cur.e = edge[cur.e].nxt;
    if (cur.e!=0){
      stk.push(cur);
      if (edge[cur.e].to!=cur.f){
        stk.push({edge[cur.e].to, cur.u, -1});
      }
    }

  }
}
// 递归查找每个节点的深度
void dfs(int i, int fat){
  depth[i] = depth[fat]+1;
  st[i][0]=fat;
  for (int p = 1;(1<<p)<=depth[i];p++){
    st[i][p] = st[st[i][p-1]][p-1]; // 跳
  }
  for (int e = head[i]; e; e = edge[e].nxt){
    if (edge[e].to!=fat){
      dfs(edge[e].to, i);      
    }
  }
}
// 开始向上走寻找
int lca(int a, int b){
  // 将深度大的设为a，深度小的设为b
  if (depth[a]<depth[b]){
    int temp = a;
    a = b;
    b = temp;
  }
  // 让更深的a上跳
  for (int p = power; p>=0; p--){
    if (depth[st[a][p]]>=depth[b]){ // 保证上跳不超过b
      a = st[a][p];
    }
  }
  // 特判来到同一层时两者相同，即b是a的祖先
  if (a==b){
    return a;
  }
  // 到达同一层，开始上跳，保证每次上跳两者不到同一节点
  for (int p = power; p>=0; p--){
    if (st[a][p]!=st[b][p]){
      a = st[a][p];
      b = st[b][p];
    }
  }
  return st[a][0];
}
void solve() {
  
  cin >> n >> m >> s;
  for (int i = 1;i<n;i++){
    int u, v;
    cin >> u >> v;
    add_edge(u,v);
    add_edge(v,u);
  }
  power = log2(n);
  cnt = 1;
  //dfs_stack(s,0);
  dfs(s,0);
  while(m--){
    int a, b;
    cin >> a >> b;
    cout << lca(a,b)<<endl;
  }
}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}

Tarjan算法

Tarjan将所有询问存储，并在dfs中离线处理

步骤：

• 建好每个节点的问题列表，并遍历树，即建立两节点之间的关系，双向
• 来到当前节点cur，标记vis数组为true，表示当前节点已经访问
• 遍历cur的所有子树，每棵子树遍历完后和cur节点合并，cur为头节点

​ 此时cur为该节点子树节点集合的头节点

• 遍历完所有子树后，处理cur节点的每一条查询(cur, x)
  • 若x已经访问过，则cur与x的最低公共祖先 = x所在集合头节点
  • 若没有访问过，则先不处理，等到x节点时再去处理(x, cur)得到答案

时间复杂度：\(O(n+m)\)

只能离线查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
int n, m, s;
int tcnt, qcnt;
int headt[N], headq[N];
int vis[N], ans[N], disj[N];
// 储存树
struct node{
  int to, nxt;
}edge[2*N];
// 储存询问
struct node2{
  int to, idx, nxt;
}query[2*N];
// 对树加边
void add_tedge(int from, int to){
  edge[++tcnt].to = to;
  edge[tcnt].nxt = headt[from];
  headt[from] = tcnt;
}
// 对询问加边
void add_qedge(int from, int to, int i){
  query[++qcnt].to = to;
  query[qcnt].nxt = headq[from];
  query[qcnt].idx = i;
  headq[from] = qcnt;
}
// 并查集查找操作
int find(int x){
  if (disj[x]!=x) disj[x] = find(disj[x]);
  return disj[x];
}
void tarjan(int u, int f){
  vis[u] = 1; // 当前节点已访问
  // 遍历该节点的孩子
  for (int e = headt[u], v; e; e=edge[e].nxt){
    v = edge[e].to;
    if (v!=f){ // 孩子和父节点不能相同
      tarjan(v,u); // 递归，让现在的孩子作为子过程的父亲节点
      disj[v] = u; // 子树头节点改为当前节点，即合并
    }
  }
  // 开始处理问题
  for (int e = headq[u], v; e; e=query[e].nxt){
    v = query[e].to;
    if (vis[v]){ // 问题已遍历，可以处理
      ans[query[e].idx]=find(v); // 问题编号位置找到v所在集合的头节点，填入ans即为答案
    }
  }
}
void solve() {
  cin >> n >> m >> s;
  for (int i = 1;i<=n;i++){
    disj[i]=i;

  }
  qcnt = tcnt = 1;
  for (int i = 1;i<n;i++){
    int u, v;
    cin >> u >> v;
    add_tedge(u, v);
    add_tedge(v, u);
  }
  for (int i = 1; i<=m;i++){
    int u, v;
    cin >> u >> v;
    add_qedge(u, v, i);
    add_qedge(v, u, i);
  }
  tarjan(s, 0);
  for (int i = 1;i<=m;i++){
    cout << ans[i]<<endl;
  }
}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}