Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
最近公共祖先
带查询的节点为x和y节点，书的深度为d
- 暴力求解：设置访问数组vis[N],以此遍历x的父节点并做标记，然后再遍历y的父节点，第一个被做标记的就是公共祖先，时间复杂度为O(d)
- 倍增法：f[i][j]代表当前节点向上走 2 j 2^j 2j所能走到的节点，其中 0 ≤ j ≤ ⌈ l o g ( d ) ⌉ 0\leq j \leq \lceil log(d) \rceil 0≤j≤⌈log(d)⌉，时间复杂度为O(logn)，另外还需要设置dist[N]代表节点i到根的距离+1，哨兵：如果从i开始跳 2 j 2^j 2j步会跳过根节点，那么f[i][j] = 0,dist[root]=0
- Tarjan离线算法：将每一个搜索过的点归类到他的代表节点中去，代表节点就是搜索过的节点与当前节点的公共祖先。时间复杂度O(n)
倍增法
- 先将两个点跳到同一层
- 再让两个点往上跳，一直跳到他们的公共祖先的下一个几点。我们跳的时候是基于二进制拼凑的思想，从最高位到最低位判断。
预处理f[i][j]时间复杂度：nlog(n)
查询O(logn)
倍增法(bfs)代码
int fa[N][16],depth[N];
int q[N],hh = 0,tt = 0;
int head[N],cnt;
struct Edge{
int v,next;
}edge[M];
void add(int u,int v){
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void bfs(int root){
//预处理
memset(depth,INF,sizeof depth);
q[0] = root;
depth[0] = 0;
depth[root] = 1,fa[root][0] = 0;
while(hh <= tt){
int t = q[hh ++];
for(int i = head[t];~i;i = edge[i].next){
int ver = edge[i].v;
if(depth[ver] < depth[t] + 1)continue;
depth[ver] = depth[t] + 1;
q[++ tt] = ver;
fa[ver][0] = t;
for(int k = 1;k < 16;k ++){
fa[ver][k] = fa[fa[ver][k - 1]][k - 1];
}
}
}
}
int lca(int a,int b){
if(depth[a] < depth[b])swap(a,b);
for(int k = 15;k >= 0;k --)
if(depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if(a == b)return a;
for(int k = 15;k >= 0;k --)
if(fa[a][k] != fa[b][k]){
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
Tarjan
struct Edge{
int v,next;
}edge[M];
void add(int u,int v){
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void init(){
for(int i = 0;i < N;i ++)fa[i] = i;
}
int Find(int x){
return fa[x] = (fa[x] == x ? x : Find(fa[x]));
}
void Tarjan(int u,int f){
vis[u] = true;
for(auto &q : query[u]){
int y = q.x,id = q.y;
if(vis[y])res[id] = Find(y); //如果之前遍历过另一个节点
}
for(int i = head[u];~i;i = edge[i].next){
int ver = edge[i].v;
if(ver == f)continue;
Tarjan(ver,u);
fa[ver] = u;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168771.html原文链接：https://javaforall.net
