首页 > 代码库 > 最近公共祖先
最近公共祖先
LCA算法
朴素算法
class Node: val = 0 left = right = None def __init__(self, val=0): self.val = val def getLCA(current, p, q): left_val, right_val = p.val, q.val parent = Node() # 保证左结点的值小于右结点 if left_val > right_val: left_val, right_val = right_val, left_val while True: if current.val > right_val: parent = current current = current.left elif current.val < left_val: parent = current current = current.right elif current.val == left_val or current.val == right_val: return parent.val else: return current.val
def getLCA2(root, node1, node2): if root == None: return None if root == node1 or root == node2: return root left = getLCA2(root.left, node1, node2) right = getLCA2(root.right, node1, node2) if left != None and right != None: return root elif left != None: return left elif right != None: return right else: return None
Tarjan算法
如何理解
- 遍历一个点,指定一个唯一时间戳DFN[i],指定该点向前追溯可追溯到的最老时间戳LOW[i];
- 枚举当前点所有边,若DFN[j]=0表明未被搜索过,递归搜索之;
- 若DFN[j]不为0,则j被搜索过,这时判断j是否在栈中,且j的时间戳DFN[j]小于当前时间戳DFN[i],可判定成环.将LOW[i]设定为DFN[j];
- 若这个点LOW[i]和DFN[i]相等,说明这个节点是所有强连通分量的元素中在栈中最早的节点,也就是我们要找的跟;
- 弹栈,将这个强连通分量全部弹出,缩成点。
- DFN[i]:表示结点 i 在DFS中是第几个被访问到的结点,称为时间戳;
- LOW[i]:表示结点 i 出发,通过有向边可以到达的所有结点中最小的index;
- 栈:存储当前已经访问过,但是没有被归类为任何的一个强连通分量的结点;
void tarjan(int i)//Tarjan { int j; DFN[i]=LOW[i]=++Dindex;//Index 时间戳 instack[i]=true;//标记入栈 Stap[++Stop]=i;//入栈 for (edge *e=V[i];e;e=e->next)//枚举所有相连边 { j=e->t;//临时变量 if (!DFN[j])//j没有被搜索过 { tarjan(j);//递归搜索j if (LOW[j]<LOW[i])//回溯中发现j找到了更老的时间戳 LOW[i]=LOW[j];//更新能达到老时间戳 } else if (instack[j] && DFN[j]<LOW[i])//如果已经印有时间戳 且 时间戳比较小,则有环 LOW[i]=DFN[j];//当前记录可追溯时间戳更新 } if (DFN[i]==LOW[i])//可追溯最小的index是自己,表明自己是当前强连通分量的跟 { Bcnt++;//强连通分量数增加 //在当前结点之后入栈并且还不属于其它的强连通分量的结点构成以当前结点为跟的强连通分量 do { j=Stap[Stop--];//出栈顶元素 instack[j]=false;//标记出栈 Belong[j]=Bcnt;//记录j所在的强连通分量编号 } while (j!=i);//如果是当前元素,弹栈完成 } } void solve() { int i; Stop=Bcnt=Dindex=0; memset(DFN,0,sizeof(DFN));//标记为为搜索过 for (i=1;i<=N;i++) // 确保所有结点都被访问到 if (!DFN[i]) tarjan(i); }
其它
参考
最近公共祖先
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。