一元夺宝网站建设,江西建设职业技术学院官方网站,wordpress首页显示摘要,深圳网站设计公司电话题目
现有一个含 n 个顶点的 双向 图#xff0c;每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示#xff0c;其中 edges[i] [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接#xff0c;并且不存在与自身相连的顶点。 返回图中 …题目
现有一个含 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的奇数长度的环假定其长度为len21环上有两个点距离x为len假定先处理的为x1,后处理的为x2。处理x1-x2是发现此环。假定此环长为偶数假定其长度为len22。环上有两个点距离x为len假定先处理的为x1,后处理的为x2。距离x为len1的点为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, vectorvector 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 vectorvector vNeiB, int src) { int n vNeiB.size(); vectorunordered_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, vectorvectorint 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 vectorvectorint vNeiB, int src){int n vNeiB.size();vectorint vDis(n, -1), vPre(n,-1);queueint 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 vectorvector vNeiB, int src) { int n vNeiB.size();
vectorint vDis(n, -1);
queueint 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, vectorvector edges) { m_iN n; m_vNeiB.resize(n); for (const autov : 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::vectorint vDis(m_iN, -1);vDis[iRoot] 0;std::queuepairint,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]);}}}
}
vectorstd::vectorint 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 C17
相关下载
算法精讲《闻缺陷则喜算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
