题目
现有一个含 n 个顶点的 双向 图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。
返回图中 最短 环的长度。如果不存在环，则返回 -1 。
环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。
2 <= n <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= ui, vi < n
ui != vi
不存在重复的边
分析
返回还是真环
利用BFS求到A的最短距离，B和C到A的距离都为1，处理BC是发现B和Ｃ都已经和A连通，说明存在环。注意：求EFG到点D的距离，处理完DE ED EF FE FG后，处理GF，发现F和G都和D连通。判断是返回，还是真环有两种思路：
一，记录已经使用的双向边，枚举新边的时候，忽略。此方案容易理解。
二，记录各点的最短距离的前一点。此方案性能。
各点都要BFS
如果以H为源点，则最短的环长4。以k为源点，最短的环是3。
多个连通区域
由于所有点都会作为起点，所以所有点都会处理。和起点不连通的点不会重复处理。
不会遗漏任意环
某个包括x的奇数长度的环，假定其长度为len2+1，环上有两个点距离x为len，假定先处理的为x1,后处理的为x2。处理x1->x2是发现此环。假定此环长为偶数，假定其长度为len2+2。环上有两个点距离x为len，假定先处理的为x1,后处理的为x2。距离x为len+1的点为x3，则处理x2->x3时，发现此环。
不会误判环
发现cur和next都和源点连通，那说明next在cur之前已经处理，也就是vDis[next] <= vDis[cur]。vDis[next]不会比v[cur]小2,否则源点->next->cur更短。也就是vDis[next]和vDis[cur]相等或少1。源点到next的最短路径，不会包括cur，否则vDis[next]大于v[cur]。两者相等的情况，cur的最短路径不会包括next。少1的情况，如果cur的最短路径包括next，则最后一条边是next->cur。
方案一代码
class Solution { public: int findShortestCycle(int n, vector<vector>& edges) { CNeiBo2 neiBo(n, edges, false); for (int i = 0; i < n; i++) { Do(neiBo.m_vNeiB, i); } return (INT_MAX == m_iMinCycle) ? -1 : m_iMinCycle; } void Do(const vector<vector>& vNeiB, int src) { int n = vNeiB.size(); vector<unordered_set> setHas(n); vector vDis(n, -1); queue q; vDis[src] = 0; q.emplace(src); while (q.size()) { const auto cur = q.front(); q.pop(); for (const auto& next : vNeiB[cur]) { if (setHas[next].count(cur)) { continue; } setHas[cur].emplace(next); if (-1 != vDis[next]) { m_iMinCycle = min(m_iMinCycle, vDis[cur] + vDis[next] + 1); continue; } vDis[next] = vDis[cur] + 1; q.emplace(next); } } } int m_iMinCycle = INT_MAX; };
方案二代码
class Solution { public: int findShortestCycle(int n, vector<vector<int>>& edges) { CNeiBo2 neiBo(n, edges, false); for (int i = 0; i < n; i++) { Do(neiBo.m_vNeiB, i); } return (INT_MAX == m_iMinCycle) ? -1 : m_iMinCycle; } void Do(const vector<vector<int>>& vNeiB, int src) { int n = vNeiB.size(); vector<int> vDis(n, -1), vPre(n,-1); queue<int> q; vDis[src] = 0; vPre[src] = -1; q.emplace(src); while (q.size()) { const auto cur = q.front(); q.pop(); for (const auto& next : vNeiB[cur]) { if (-1 != vDis[next]) { if (vPre[cur] != next) { m_iMinCycle = min(m_iMinCycle, vDis[cur] + vDis[next] + 1); } continue; } vDis[next] = vDis[cur] + 1; vPre[next] = cur; q.emplace(next); } } } int m_iMinCycle = INT_MAX; };
方案三
方案一和方案二时间复杂度都是O(n^2)，方案一比方案二慢。方案三相比方案一，稍稍提速。
void Do(const vector<vector>& vNeiB, int src)
{
int n = vNeiB.size();
vector<int> vDis(n, -1); queue<int> q; vDis[src] = 0; q.emplace(src); while (q.size()) { const auto cur = q.front(); q.pop(); for (const auto& next : vNeiB[cur]) { if (m_vHasDo[next][cur]) { continue; } m_vHasDo[cur][next] = 1; if (-1 != vDis[next]) { m_iMinCycle = min(m_iMinCycle, vDis[cur] + vDis[next] + 1); continue; } vDis[next] = vDis[cur] + 1; q.emplace(next); } }
}
2023年4月版本
class Solution { public: int findShortestCycle(int n, vector<vector>& edges) { m_iN = n; m_vNeiB.resize(n); for (const auto&v : edges) { m_vNeiB[v[0]].emplace_back(v[1]); m_vNeiB[v[1]].emplace_back(v[0]); }
for (int i = 0; i < n; i++) { bfs(i); } return (INT_MAX == m_iRet) ? -1 : m_iRet; } void bfs(int iRoot) { std::vector<int> vDis(m_iN, -1); vDis[iRoot] = 0; std::queue<pair<int,int>> que; que.emplace(iRoot, -1);//当前节点，父节点 while (que.size()) { const int iPre = que.front().first; const int iPrePre = que.front().second; que.pop(); for (const auto& next : m_vNeiB[iPre]) { if (-1 == vDis[next]) { vDis[next] = vDis[iPre] + 1; que.emplace(next, iPre); } else { if (next == iPrePre) { continue; } m_iRet = min(m_iRet, vDis[iPre] + 1 + vDis[next]); } } } } vector<std::vector<int>> m_vNeiB; int m_iN; int m_iRet = INT_MAX;
};
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
