描述
小明的實驗室有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;
} 複制