您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

2017蓝桥杯C/C++B组国赛-发现环

不牌不改 发布时间:2022-03-16 10:59:08 ,浏览量:0

题目

题目链接

题解

并查集 + 最近公共祖先。

整体思路:

并查集用于判断是否出现环,出现环就记录下来导致环的边两端的点,求两个点的最近公共祖先,从两个端点向上找到全部的祖先直到二者的最近公共祖先,排序输出。

思路太清晰了,就是看你有没有背过模板。

(看到这个题秒出思路,但是忘记怎么写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             
关注
打赏
1662186765
查看更多评论
0.0490s