最短 等边权 显然bfs
lc2308
以是否在队列里 为判断条件
归为 最小路径树
dfs实现第二次遇到的设计 fa
auto [x, fa] = q.front()
if (dis[y]＞＝0 && y != fa) // 第二次遇到
ans = min(ans, dis[x] + dis[y] + 1);
class Solution {
public:
int findShortestCycle(int n, vector<vector<int>> &edges) {
vector<vector<int>> g(n);
for (auto &e: edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x); // 建图
}
int dis[n];
// dis[i] 表示从 start 到 i 的最短路长度
auto bfs = [&](int start) -> int {
int ans = INT_MAX;
memset(dis, -1, sizeof(dis));
dis[start] = 0;
queue<pair<int, int>> q;
q.emplace(start, -1);
while (!q.empty()) {
auto [x, fa] = q.front();
q.pop();
for (int y: g[x])
if (dis[y] < 0) { // 第一次遇到
dis[y] = dis[x] + 1;
q.emplace(y, x);
}else if (y != fa) // 第二次遇到
ans = min(ans, dis[x] + dis[y] + 1);
}
return ans;
};
int ans = INT_MAX;
for (int i = 0; i < n; ++i) // 枚举每个起点跑 BFS
ans = min(ans, bfs(i));
return ans < INT_MAX ? ans : -1;
}
};
)
)
