【POJ 1330 Nearest Common Ancestors】LCA问题 Tarjan算法

  • 时间:
  • 浏览:0

每遍历完一棵子树r,把它并入以r的父节点p为代表元的集合。这时判断p是都在所要求的u, v节点之一,肯能r==u,且v已访问过,则lca(u, v)必为v所属集合的代表元。p==v的情况汇报类似。

注意题目给树的格式:给出n-另有三个白 多数对<u, v>,u为v的父节点。之后 都可不可不都可以当作有向图用邻接表存储,一齐记录各个节点的入度,入度为0的点为树根。

题意:给定另有三个白 多n个节点的有根树,以及树中的另有三个白 多节点u,v,求u,v的最近公共祖先。

题目链接:http://poj.org/problem?id=1350

思路:从树根出发进行后序深层优先遍历,设置vis数组实时记录不是已被访问。

我的第一道LCA什么的难题的Tarjan算法,题目不到唯一的一组查询,实现起来非常简洁。

数据范围:n [2, 500]