[C++知识库]2017蓝桥杯C/C++B组国赛-发现环

题目

题目链接

题解

并查集 + 最近公共祖先。

整体思路：

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

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

（看到这个题秒出思路，但是忘记怎么写LCA了，看了看yxc，直接一发入魂）

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int idx, e[N<<1], ne[N<<1], h[N];
int fa[N][30], dp[N], p[N];
int n, a, b, aa, bb;
vector <int> v;

void add (int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int find (int x) {
	return x == p[x] ? p[x] : p[x] = find (p[x]);
}

void bfs () {
	memset (dp, 0x3f, sizeof dp);
	dp[0] = 0, dp[1] = 1;
	
	queue<int> q;
	q.push (1);
	
	while (q.size ()) {
		int t = q.front ();
		q.pop ();
		
		for (int i = h[t];~i;i = ne[i]) {
			int j = e[i];
			if (dp[j] > dp[t] + 1) {
				dp[j] = dp[t] + 1;
				q.push (j);
				fa[j][0] = t;
				for (int k = 1;k <= 20;k ++)
					fa[j][k] = fa[fa[j][k-1]][k-1];
			}
		}
	}
}

int lca (int a, int b) {
	if (dp[a] < dp[b]) swap (a, b);
	
	for (int k = 20;k >= 0;k --) 
		if (dp[fa[a][k]] >= dp[b])
			a = fa[a][k];
			
	if (a == b) return a;
	
	for (int k = 20;k >= 0;k --)
		if (fa[a][k] != fa[b][k])
			a = fa[a][k],
			b = fa[b][k];
			
	return fa[a][0];
}

int main()
{
	memset (h, -1, sizeof h);
	
	cin >> n;
	for (int i = 1;i <= n;i ++) p[i] = i;
	for (int i = 1;i <= n;i ++) {
		cin >> 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 < v.size ();i ++)
		cout << v[i] << ' ';
	
	return 0;
}