蓝桥杯2017年第八届真题-发现环 （C语言代码）

解题思路:

注意事项:

注意如果找到了解，不要回溯，因为回溯回去啥都回溯没了，所有找到解之后先打印完之和，直接退出程序，不需要回溯，还节约程序执行时间

参考代码:

#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 1e5 +10;
int pre[N], vis[N];
vector<int> E[N];
set<int> path;
void Init() {
	for(int i = 0; i < N; ++i) pre[i] = i;
} 

int find(int x) { // 递归 （数据量大的时候使用迭代，因为递归会爆栈）
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

//int find(int x) { // 迭代
//	int p = x, tmp;
//	while(x != pre[x]) x = pre[x];
//	while(p != x) {
//		tmp = pre[p];
//		pre[p] = x;
//		p = tmp;
//	}
//	return x;
//}

bool Union(int x, int y) {
	int x_root = find(x);
	int y_root = find(y);
	if(x_root != y_root) {
		pre[x_root] = y_root;
		return true;
	}
	return false;
}

void dfs(int s, int t) {
	if(s == t) {
		for (set<int>::iterator it = path.begin(); it != path.end(); ++it) {
			if (it != path.begin()) cout << ' ';
			cout << *it;
		}
		exit(0); // 找到了及时退出
	}
	for(int i = 0; i < E[s].size(); ++i) {
		int u = E[s][i];
		if(vis[u]) continue;
		vis[u] = 1;
		path.insert(u);
		dfs(u, t);
		vis[u] = 0;
		path.erase(u);
	}
}

int main() { 
	int n, x, y, from, to;
	scanf("%d", &n);
	Init();
	for(int i = 0; i < n; ++i) {
		scanf("%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
		if(find(x) != find(y)) {
			Union(x, y);
		} else {
			from = x, to = y;
		}
	}
	path.insert(from);
	dfs(from, to);
	return 0;
}