LCA（最近公共祖先）算法
2021-05-18 21:28
标签：ref soscw https port 离线 com class tor 关系 参考博客：https://blog.csdn.net/my_sunshine26/article/details/72717112 首先看一下定义，来自于百度百科 LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 注意：这里某个节点本身也是它的祖先节点。 求最近公共祖先的算法： 1、暴力：每次查询的时间复杂度为O(N) 2、Tarjan（离线）算法：在一次遍历中把所有查询解决，预处理时间复杂度O(nlogn),每次查询时间复杂度O(1)，总时间复杂度是O(nlogn+q) 3、倍增算法：利用二分两个节点同时往上走，直到相遇，预处理时间复杂度O(nlogn)，每次查询时间复杂度O(logn) 首先让u和v中较深的一个往上走|depth(u)-depth(v)|步，然后再一起一步步往上走，直到走到同一个节点，就可以在O(depth(u)+depth(v))的时间内求出LCA。 关键在于如何优化向上查找的过程 分析刚才的算法，两个节点到达同一节点后，不论怎么向上走，达到的显然还是同一节点。利用这一点，我们就能够利用二分搜索求出到达最近公共祖先的最小步数了。 首先我们要进行预处理。对于任意的节点，可以通过fa2[v]=fa[fa[v]]得到其向上走2步到达的顶点，再利用这个信息，又可以通过fa4[v]=fa2[fa2[v]]得到其向上走4步所到的顶点。以此类推，我们可以得到其向上走2^k步所到的顶点fa[v][k],预处理的时间点复杂度为O(nlogn)。 LCA（最近公共祖先）算法 标签：ref soscw https port 离线 com class tor 关系 原文地址：https://www.cnblogs.com/yanchaoyi/p/9741958.html
Tarjan（离线）算法
一.Tarjan算法大致实现过程
二.Tarjan算法的伪代码
1 Tarjan(u) //根节点u
2 {
3 for each(u,v)
4 {
5 Tarjan(v); //v还有儿子节点
6 join(u,v); //把v合并到u上
7 vis[v]=1; //访问标记
8 }
9 for each(u,v) //遍历与u有询问关系的节点v
10 {
11 if(vis[v])
12 {
13 ans=find(v);
14 }
15 }
16 }
三.Tarjan算法的代码
1 void Tarjan(int u)
2 {
3 vis[u]=1;
4 for(int i=0;i
倍增算法
一、算法铺垫
二.倍增算法的实现过程
1 void init()
2 {
3 lg[1]=0;
4 for(int i=2;i)
5 lg[i]=lg[i-1]+(11]+1)==i);//用来求log2(n)
6 }
7 void dfs(int f,int fath)
8 {
9 deepth[f]=deepth[fath]+1;
10 fa[f][0]=fath;
11 for(int i=1;(1)
12 fa[f][i]=fa[fa[f][i-1]][i-1];
13 for(int i=0;i