「学习笔记」tarjan 求最近公共祖先

这篇具有很好参考价值的文章主要介绍了「学习笔记」tarjan 求最近公共祖先。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Tarjan 算法是一种 离线算法,需要使用并查集记录某个结点的祖先结点。
并没有传说中的那么快。

过程

将询问都记录下来,将它们建成正向边和反向边。
在 dfs 的过程中,给走过的节点打上标记,同时维护并查集,这里利用了回溯的思想,如果 \(u\) 节点的这棵子树没搜完,那么 fa[u] = u;,搜完后,在更新并查集。
我们假设查询 \(u\)\(v\) 的最近公共祖先,搜到节点 \(u\),如果另一个节点 \(v\) 已经被搜到过了,那么 \(v\) 点的并查集祖先就是 \(u\)\(v\) 的最近公共祖先。

如果第一次查询 \(v\) 点时,发现 \(v\) 点已经被搜到了,说明 \(u\)\(v\) 点在同一棵子树中,并且这个子树是所有包括了 \(u\) 点和 \(v\) 点的子树中 siz 最小的,这棵子树的根也是在所有符合条件的子树的根中离 \(u\)\(v\) 最近的,即这棵子树的根就是 \(u\)\(v\) 的最近公共祖先,而 \(v\) 的并查集祖先就是这个根节点。

代码

结构体记录询问

int cnt = 1;

struct query {
	int v, lca, nxt;
} q[N << 1];

记录询问、初始化

for (int i = 1, x, y; i <= m; ++ i) {
	scanf("%d%d", &x, &y);
	add_query(x, y);
	add_query(y, x);
}
for (int i = 1; i <= n; ++ i) {
	fa[i] = i;
}

tarjan、并查集

void tarjan(int u) {
	fa[u] = u;
	vis[u] = 1;
	for (int v : son[u]) {
		if (!vis[v]) {
			tarjan(v);
			fa[v] = u;
		}
	}
	int v;
	for (int i = h[u]; i; i = q[i].nxt) {
		if (vis[v = q[i].v]) {
			q[i].lca = q[i ^ 1].lca = find(v);
		}
	}
}

fa[u] = u; 是为了保证在 \(u\) 这棵子树没有搜完的情况下,让它子树里的节点的并查集找祖先时找到的是它。文章来源地址https://www.toymoban.com/news/detail-429730.html

到了这里,关于「学习笔记」tarjan 求最近公共祖先的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 更快的求最近公共祖先(LCA)的算法-倍增法求LCA

    236. 二叉树的最近公共祖先 参考:最近公共祖先 f a [ i ] [ j ] rm{fa}[i][j] fa [ i ] [ j ] 表示结点 i i i 的第 2 i 2^i 2 i 个组先 d e p [ i ] rm{dep}[i] dep [ i ] 表示结点 i i i 的深度 n e x t [ i ] [ 0 ] rm{next}[i][0] next [ i ] [ 0 ] 表示结点 i i i 的左子结点 n e x t [ i ] [ 1 ] rm{next}[i][1] next [ i ] [ 1 ]

    2024年02月12日
    浏览(33)
  • DAY23:二叉树(十三)二叉树的最近公共祖先+二叉搜索树的最近公共祖先

    一定要仔细看 提示 ,二叉树 数值不重复 ,意味着后序遍历不会存在两边找到了同个元素的情况 本题需要进一步理解后序遍历, 可以认为后序遍历在\\\"深入\\\"到每个子树的最深层之后,才开始\\\"回溯\\\"并访问节点 。 在某种意义上,这可以被视为从下往上的遍历方式 , 但需要注

    2024年02月09日
    浏览(43)
  • 图论--最近公共祖先LCA

    LCA(Least Common Ancestors),即最近公共祖先,是指这样一个问题:在有根树中,找出某两个结点u和v最近的公共祖先(另一种说法,离树根最远的公共祖先) 最近公共祖先是相对于两个节点来说的,一般来说,最近公共祖先为节点 u和节点 v的最近的公共祖先。若 u 为 v 的祖先

    2024年02月03日
    浏览(40)
  • 最近公共祖先(LCA)

    「观前提醒」 「文章仅供学习和参考,如有问题请在评论区提出」 目录 前言 定义 性质 求 LCA 倍增算法 Trajan 算法 树链剖分 基本概念 基本性质 具体实现 参考资料 简单的模板整理,只是概括了一下具体的实现方法(说到底是给自己写的),如果看不明白可以去看原视频(讲

    2024年02月14日
    浏览(35)
  • Tarjan算法

    1 算法简介 还记得 无向图判连通块 吗?对于无向图中,判连通块是一件很容易的事。你只需要 dfs(深度优先搜索) 一下就可以了。但是,如果我们把无向图换成 有向图 呢? 这就是另一个故事了… 2 算法定义 Robert Tarjan 计算机科学家,以 LCA , Tarjan 等算法闻名。 Tarjan 是求强连

    2024年02月14日
    浏览(35)
  • 浅谈 Tarjan 算法

    在了解 Tarjan 算法之前,我们先来了解 dfs 搜索树。 定义: dfs 遍历整张图,按照 dfs 序构成一棵树。 1.1 有向图的 dfs 生成树 有向图的 dfs 生成树包括四种边: 树边(tree edge):图中黑色边表示。表示搜索访问到未访问过的结点。 回边(back edge):图中橙色边表示。表示该边

    2024年02月05日
    浏览(37)
  • Tarjan 算法(超详细!!)

    推荐在 cnblogs 上阅读 说来惭愧,这个模板仅是绿的算法至今我才学会。 我还记得去年 CSP2023 坐大巴路上拿着书背 Tarjan 的模板。虽然那年没有考连通分量类似的题目。 现在做题遇到了 Tarjan,那么,重学,开写! 另,要想学好此算法的第一件事——膜拜 Tarjan 爷爷。 其实广义

    2024年01月25日
    浏览(41)
  • 算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先

    递归 递归中保存前一个节点的指针的方法,需要再学习,巩固一下 迭代 一下子就想到的方法:遍历一遍二叉搜索树,把各个节点的值存进哈希表里(节点值——键,出现频率——值),再遍历哈希表找众数 一般方法 既然是二叉搜索树,中序遍历就是有序的。有序的话,我

    2024年02月16日
    浏览(43)
  • 力扣236——二叉树的最近公共祖先

    祝大家新年快乐呀,虽这段时间正值过年,但是我们不要忘记停下学习的脚步。今天我们一起看一到力扣上的经典二叉树OJ题,求二叉树两个结点最近的公共祖先。 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 链接给大家放在这里啦,大家一点即达 首先我们

    2024年02月20日
    浏览(40)
  • 【图论】无向图连通性(tarjan算法)

    1. 连通 : 在图论中,连通性是指一个无向图中的任意两个顶点之间存在路径。如果对于图中的任意两个顶点 u 和 v,存在一条路径从 u 到 v,那么图被称为连通图。如果图不是连通的,那么它可以被分为多个 连通分量 ,每个连通分量都是一个连通子图。 2.割点: 割点(Cut V

    2024年02月13日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包