蓝桥杯2017年第八届真题-发现环

题目

题目链接

题解

并查集+DFS。

并查集比较明显，因为要判断有没有环； 思路也很简单，若不停加边，若两个点的fa是一样的，则说明再加上这两点之间的直接 边就会出现环，因此这两个点一定位于环上； 我们以两点中的其中一个点为起点，dfs寻找另一个点，记录dfs路径上选择的点，当到达另一个点时，说明找完了环上的点，排序输出即可。

注意find函数路径压缩，否则超时。

代码中还有一些降低时间复杂度的细节操作，详见代码。

代码

#include
using namespace std;
const int N = 1e6+10;

int n, a, b, ss, tt, flag, fflag;
int res[N], fa[N], vis[N];

vector v[N];

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]); // 必须进行路径压缩，否则超时 
}

void dfs(int x, int cnt) {
	
	if(flag) return ; // 当找到答案之后，flag设置为1，遇到1直接返回，降低时间复杂度 
	
	if(x == tt) {
		flag = 1;
		sort(res, res+cnt);
		for(int i = 0;i