LCA问题的Tarjan算法 >> NoAlGo博客

LCA问题的Tarjan算法 » NoAlGo博客

LCA问题（Least Common Ancestors，最近公共祖先问题），是指给定一棵有根树T，给出若干个查询LCA(u, v)（通常查询数量较大），每次求树T中两个顶点u和v的最近公共祖先，即找一个节点，同时是u和v的祖先，并且深度尽可能大（尽可能远离树根）。 一 LCA问题 算法从根节点root开始搜索，每次递归搜索所有的子树，然后处理跟当前根节点相关的所有查询。 其中关于集合的操作都是使用并查集高效完成。 算法的复杂度为，O(n)搜索所有节点，搜索每个节点时会遍历这个节点相关的所有查询。如果总的查询个数为m，则总的复杂度为O(n+m)。 比如上面的例子中，前面处理的节点的顺序为4->7->5->1->0->…。 当访问完4之后，集合{4}跟集合{1}合并，得到{1,4}，并且集合祖先为1。然后访问7。如果(7,4)是一个查询，由于4已访问过，于是LCA(7,4)为4所在集合{1,4}的祖先，即1。7访问完之后，把{7}跟{5}合并，得到{5,7}，祖先为5。然后访问5。如果(5,7)是一个查询，由于7已访问过，于是LCA(5,7)为7所在集合{5,7}的祖先，即5。如果(5,4)也是一个查询，由于4已访问过，则LCA(5,4)为4所在集合{1,4}的祖先，即1。5访问完毕之后，把{5,7}跟{1,4}合并，得到{1,4,5,7}，并且祖先为1。然后访问1。如果有(1,4)查询，则LCA(1,4)为4所在集合{1,4}的祖先，为1。1访问完之后，把{1,4,5,7}跟{0}合并，得到{0,1,4,5,7}，祖先为0。然后剩下的2后面的节点处理类似。 三 算法实现 使用邻接表方法存储一棵有根树。并通过记录节点入度的方法找出有根树的根，方便后续处理。 const int mx = 10000; //最大顶点数 int n, root; //实际顶点个数，树根节点 int indeg[mx]; //顶点入度，用来判断树根 vector tree[mx]; //树的邻接表（不一定是二叉树） void inputTree() //输入树 { scanf("%d", &n); //树的顶点数 for (int i = 0; i < n; i++) //初始化树，顶点编号从0开始 tree[i].clear(), indeg[i] = 0;

Read full article from LCA问题的Tarjan算法 » NoAlGo博客