題意#
Byteland 上有 \(n\) 座城市以及 \(m\) 條雙向道路。你的任務是規劃一趟「環島旅行（Round Trip）」。
這趟旅行必須從某個城市出發，經過至少兩座「不重複」的其他城市之後，最後再回到原來的出發城市（路徑上總共會經過至少 4 個城市，包含頭尾）。請先印出這趟旅程總共造訪的城市數量，再將路線照順序印出來。如果根本找不到任何合適的路線，就霸氣地印出 IMPOSSIBLE。
思路#
雖然題目包裝成規劃旅行，但本質上這就是在尋找「無向圖中的環（Cycle）」。
要在無向圖中找環，最常見的手法就是深度優先搜尋（DFS）。每走到一個城市，我們就不斷往相鄰的城市深掘。為了避免陷入死胡同，我們會記錄下「這一步是從哪個城市走過來的（父節點）」，這樣下一步就不會傻傻地又走原路退回去。
如果在 DFS 推進的過程中，我們某天突然碰上了一個「已經造訪過」而且「不是父節點」的城市，恭喜！這就代表我們走到了一條能繞回過去的捷徑（Back Edge），抓到了傳說中的環。
這時我們只要拿出剛剛記錄的「父節點陣列（vis）」，從現在這個引爆環的節點開始，沿著指標一路往上倒推，把它們全部塞進這個環的答案陣列中。因為這是一條從尾端開始「倒吞」回去的路徑，而且 DFS 出來的環通常已經能滿足經過 3 個不同節點的最低要求了。將陣列再接上原始點收起口後，就是一條完美的環狀路線。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
vector<vector<int>> v;
// vis 在本題一物兩用：
// 未造訪是 0，如果被造訪過，就會存「上一個踏足的節點（父節點）」來當作回推路徑用
vector<int> vis, ans;
// DFS 尋找環，pre 用來記錄「上一步是哪個節點」，避免在雙向邊上直接倒退擼
void dfs(int x, int pre) {
for (auto u : v[x]) {
if (u == pre) continue; // 不可以走回頭路
// 如果這個點沒走過，就記錄他是從 x 來的，並繼續深搜
if (!vis[u]) {
vis[u] = x;
dfs(u, x);
}
else {
// 抓到環了！（撞到已經走過且不是爸爸的節點 u）
// 此時 x 是目前節點，u 是環的交叉點
ans.pb(x);
// 沿著 vis 的紀錄不斷往回倒推，直到退回交叉點 u 形成閉環
while (ans.back() != u) ans.pb(vis[ans.back()]);
ans.pb(x); // 補上最後的缺口，讓頭尾相連
cout << ans.size() << '\n';
for (auto &i : ans) cout << i << ' ';
exit(0); // 找到任意一個環就能交差，直接終止程式
}
}
}
signed main() { WA();
int n, m; cin >> n >> m;
v.resize(n+1);
vis.resize(n+1);
// 建立雙向圖
while (m--) {
int a, b; cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
}
// 可能有多個不連通的區域，所以每個點都要當起點試試看
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = i; // 標記起點本身，避免被誤認為未造訪 (0)
dfs(i, 0); // 第一步的父節點傳入 0 規避碰撞
}
}
// DFS 把所有的點都逛完了卻沒呼叫過 exit(0)，代表這張圖是森林（無環）
cout << "IMPOSSIBLE\n";
}
