描述
小明的实验室有 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;
- }
来源: http://www.bubuko.com/infodetail-2600832.html