题目
题目链接
题解并查集 + 最近公共祖先。
整体思路:
并查集用于判断是否出现环,出现环就记录下来导致环的边两端的点,求两个点的最近公共祖先,从两个端点向上找到全部的祖先直到二者的最近公共祖先,排序输出。
思路太清晰了,就是看你有没有背过模板。
(看到这个题秒出思路,但是忘记怎么写LCA了,看了看yxc,直接一发入魂)
代码#include
using namespace std;
const int N = 1e5+10;
int idx, e[N n;
for (int i = 1;i a >> b;
int ra = find (a), rb = find (b);
if (ra != rb) { // 祖先不同说明二者还没连通
p[ra] = rb;
add (a, b);
add (b, a);
}
else // 已经连通了又加了一条边,形成了环
aa = a, bb = b;
}
bfs ();
int prt = lca (aa, bb);
v.push_back (prt); // 从 aa 和 bb 开始每次向上走一步,即找到直接父亲节点,直到走到最近公共祖先,这些点就是环路上的点
while (aa != prt) v.push_back (aa), aa = fa[aa][0];
while (bb != prt) v.push_back (bb), bb = fa[bb][0];
sort (v.begin (), v.end ());
for (int i = 0;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?