惠民县建设局官方网站,外汇跟单网站建设,wordpress 多语言 插件,思勤传媒网站建设公司有一个具有 n 个顶点的 双向 图#xff0c;其中每个顶点标记从 0 到 n - 1#xff08;包含 0 和 n - 1#xff09;。图中的边用一个二维整数数组 edges 表示#xff0c;其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接#x…有一个具有 n 个顶点的 双向 图其中每个顶点标记从 0 到 n - 1包含 0 和 n - 1。图中的边用一个二维整数数组 edges 表示其中 edges[i] [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 source 开始到顶点 destination 结束的 有效路径 。
给你数组 edges 和整数 n、source 和 destination如果从 source 到 destination 存在 有效路径 则返回 true否则返回 false 。 示例 1 输入n 3, edges [[0,1],[1,2],[2,0]], source 0, destination 2
输出true
解释存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2
- 0 → 2示例 2 输入n 6, edges [[0,1],[0,2],[3,5],[5,4],[4,3]], source 0, destination 5
输出false
解释不存在由顶点 0 到顶点 5 的路径.提示
1 n 2 * 1050 edges.length 2 * 105edges[i].length 20 ui, vi n - 1ui ! vi0 source, destination n - 1不存在重复边不存在指向顶点自身的边
代码
#includeiostream
#includevector
#includequeue
using namespace std;
class Solution {
public:bool validPath(int n, vectorvectorint edges, int source, int destination) {vectorvectorint adj(n);for (auto edge : edges) {int x edge[0];int y edge[1];adj[x].push_back(y);adj[y].push_back(x);}queueint qu;qu.push(source);vectorbool v(n, false);v[source] true;while (!qu.empty()) {int ver qu.front();qu.pop();if (ver destination) {break;}for (auto next : adj[ver]) {if (!v[next]) {qu.push(next);v[next] true;}}}return v[destination];}
};
int main() {int n; cin n;int col; cin col;vectorvectorint edges;edges.resize(n);for (auto i 0; i n; i) {edges[i].resize(col);for (auto j 0; j col; j) {cin edges[i][j];}}int source; cin source;int destination; cin destination;Solution solution Solution();int res solution.validPath(n, edges, source, destination);cout res endl;return 0;
}
