2017第八届蓝桥杯决赛（C++ B组）4.发现环
描述
小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。 为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
输入 第一行包含一个整数N。 以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。 对于30%的数据，1 <= N <= 1000 对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N 输入保证合法。
输出 按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。 样例输入： 5 1 2 3 1 2 4 2 5 5 3 样例输出： 1 2 3 5
思路
DFS搜索，直到找到一条可以返回起点的路径为止。 由于是无向图，需要注意一下 如果所有点都遍历了还是没找到那就直接返回,即：
if (walk.size() == n) {
return;
}而且如果发现环那么那个环上每个点出发都会输出一次，而题目只要求输出一次，所以还要保存一下当前找到的环，对应代码：
if (std::find(found.begin(), found.end(), walk) == found.end()) {
found.push_back(walk);
for (int i = 0; i < walk.size(); i++) {
std::cout << walk[i] << " ";
}
std::cout << "\n";
}
return;然后就是日常的DFS遍历了。
源码
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
int n = 0;
std::vector<std::vector<int>> found;
std::multimap<int, int> edge;
void dfs(std::vector<int> walk, int start, int current) {
if (start == current) {
std::sort(walk.begin(), walk.end());
if (std::find(found.begin(), found.end(), walk) == found.end()) {
found.push_back(walk);
for (int i = 0; i < walk.size(); i++) {
std::cout << walk[i] << " ";
}
std::cout << "\n";
}
return;
}
if (walk.size() == n) {
return;
}
auto begin = edge.lower_bound(current);
auto end = edge.upper_bound(current);
while (begin != end) {
int node = begin->second;
if (walk[walk.size() - 1] != node) {
// If we haven't visited this node
walk.push_back(current);
dfs(walk, start, node);
walk.pop_back();
}
++begin;
}
}
int main() {
std::cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
std::cin >> a >> b;
edge.insert({ a,b });
edge.insert({ b,a });
}
for (auto b = edge.begin(); b != edge.end(); ++b) {
std::vector<int> walk;
walk.push_back(b->first);
dfs(walk, b->first, b->second);
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018-05-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
