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

题目

题目链接

题解

并查集 + 最近公共祖先。

整体思路：

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

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

（看到这个题秒出思路，但是忘记怎么写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