1. 首页
  2. 编程语言
  3. 其他
  4. LCA的tarjan算法

LCA的tarjan算法

上传者: 2019-09-25 00:16:59上传 CPP文件 1.78KB 热度 49次
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后把该子节点的父亲指向该节点,当所有子节点DFS完毕后,将该节点标记为已访问,然后对和该节点有关的询问进行处理,如果另一个节点未被标记则跳过,否则这次询问的结果即是另一个节点的代表元(刘汝佳黑书里介绍很详细)
下载地址
用户评论
码姐姐匿名网友 2019-09-25 00:16:59

哇,这个绝对好东西!!初学者适用