盐城做网站网络公司电话?,软件开发文档实例,图书馆网络规划与设计,360搜索首页网址是多少1971. Find if Path Exists in Graph
有一个具有 n个顶点的 双向 图#xff0c;其中每个顶点标记从 0 到 n - 1#xff08;包含 0 和 n - 1#xff09;。图中的边用一个二维整数数组 edges 表示#xff0c;其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 …1971. Find if Path Exists in Graph
有一个具有 n个顶点的 双向 图其中每个顶点标记从 0 到 n - 1包含 0 和 n - 1。图中的边用一个二维整数数组 edges 表示其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 start 开始到顶点 end 结束的 有效路径 。
给你数组 edges 和整数 n、start和end如果从 start 到 end 存在 有效路径 则返回 true否则返回 false 。 示例 1输入n 3, edges [[0,1],[1,2],[2,0]], start 0, end 2
输出true
解释存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2
- 0 → 2示例 2输入n 6, edges [[0,1],[0,2],[3,5],[5,4],[4,3]], start 0, end 5
输出false
解释不存在由顶点 0 到顶点 5 的路径.提示:
1 n 2∗1052 * 10^52∗1050 edges.length 2∗1052 * 10^52∗105edges[i].length 20 ui, vi n - 1ui ! vi0 start, end n - 1不存在双向边不存在指向顶点自身的边
解题思路
使用map维护双向图边之间的关系key为节点编号value为一个记录与当前节点存在公共边连接的节点数组。利用队列实现广度优先搜索先将start节点入队每次从队列中取出队首节点将与该节点存在公共边并且没被访问过的节点入队直到找出end节点为止如果直到队列为空都找不到end节点说明不存在从 start 到 end 的 有效路径
代码 class Solution {
public:bool validPath(int n, vectorvectorint edges, int start, int end) {mapint,vectorint e;for(auto item:edges){e[item[0]].push_back(item[1]);e[item[1]].push_back(item[0]);}unordered_setint s;s.insert(start);queueintq;q.push(start);while (!q.empty()){int curq.front();q.pop();if (curend)return true;for (auto c:e[cur]) {if (!s.count(c)){q.push(c);s.insert(c);}}}return false;}
};
