題意#
給定一張有 $n$ 個點、 $m$ 條邊的無向圖，求出整張圖的最小環長度（圖的圍長）。如果找不到半個環，就輸出 -1。
思路#
這題 $n \le 2500, m \le 5000$ 的範圍卡在一個微妙的位置，看來 $O(nm)$ 左右的複雜度是能過的。
想找最小環，最暴力的思路就是直接對每一個點都跑一次 BFS。
為什麼選 BFS？因為它是一層層均勻向外擴散的。只要我們在搜的過程中踩到「已經被走過、而且不是剛剛走來那條邊」的點，就代表一定構成環了！再加上 BFS 先找到的一定是最短距離這項特性，這時候抓出來的環，一定會是包含該起點的環裡面最短的。
作法其實滿固定的：
- 枚舉每個點 $x$ 當起點開始 BFS。
- 過程下記錄起點到每個點的距離
dis。 - 當現在的點
now走到相鄰點to時，發現to走過了且不是last，就算是抓到環了，長度會是dis[now] + dis[to] + 1。 - 整個掃過一次，維護環長度的最小值。另外，無向圖最小的環極限就是 3，如果搜到一半挖到長度為 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;
int n, m;
int bfs(int x) {
vector<int> vis(n+1), dis(n+1);
queue<PII> q; q.push({x, 0}); vis[x] = 1;
int mn = INF;
while (q.size()) {
auto [now, last] = q.front(); q.pop();
for (auto &to : v[now]) {
if (vis[to]) {
// 如果踩到走過的點，且不是剛剛走來的那條邊，代表找到環了
if (to != last) mn = min(mn, dis[now] + dis[to] + 1);
}
else {
// 還沒走過的話就記錄距離，繼續往下搜
dis[to] = dis[now] + 1;
vis[to] = 1;
q.push({to, now});
}
}
}
return mn;
}
signed main() { WA();
cin >> n >> m;
v.resize(n+1);
while (m--) {
int a, b; cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
}
int ans = INF;
for (int i = 1; i <= n; i++) {
ans = min(ans, bfs(i));
// 無向圖最小的環長度極限就是 3，找到了直接提早收工
if (ans == 3) break;
}
if (ans == INF) cout << "-1\n";
else cout << ans << '\n';
}
