find-if-path-exists-in-graph

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is a bi-directional graph with <code>n</code> vertices, where each vertex is labeled from <code>0</code> to <code>n - 1</code> (inclusive). The edges in the graph are represented as a 2D integer array <code>edges</code>, where each <code>edges[i] = [ui, vi]</code> denotes a bi-directional edge between vertex <code>ui</code> and vertex <code>vi</code>. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex <code>source</code> to vertex <code>destination</code>.

Given <code>edges</code> and the integers <code>n</code>, <code>source</code>, and <code>destination</code>, return <code>true</code> if there is a valid path from <code>source</code> to <code>destination</code>, or <code>false</code> otherwise.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png" style="width: 141px; height: 121px;" />
<pre>
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 &rarr; 1 &rarr; 2
- 0 &rarr; 2
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png" style="width: 281px; height: 141px;" />
<pre>
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 105</code></li>
	<li><code>0 &lt;= edges.length &lt;= 2 * 105</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ui, vi &lt;= n - 1</code></li>
	<li><code>ui != vi</code></li>
	<li><code>0 &lt;= source, destination &lt;= n - 1</code></li>
	<li>There are no duplicate edges.</li>
	<li>There are no self edges.</li>
</ul>

validPath

Find if Path Exists in Graph

Valid Arrangement of Pairs

valid-arrangement-of-pairs

合法重新排列数对

Paths in Maze That Lead to Same Room

paths-in-maze-that-lead-to-same-room

殊途同归

Depth-First Search

Breadth-First Search

Union Find

Graph

有一个具有 <code>n</code> 个顶点的 双向 图，其中每个顶点标记从 <code>0</code> 到 <code>n - 1</code>（包含 <code>0</code> 和 <code>n - 1</code>）。图中的边用一个二维整数数组 <code>edges</code> 表示，其中 <code>edges[i] = [ui, vi]</code> 表示顶点 <code>ui</code> 和顶点 <code>vi</code> 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 <code>source</code> 开始，到顶点 <code>destination</code> 结束的 有效路径 。

给你数组 <code>edges</code> 和整数 <code>n</code>、<code>source</code> 和 <code>destination</code>，如果从 <code>source</code> 到 <code>destination</code> 存在 有效路径 ，则返回 <code>true</code>，否则返回 <code>false</code> 。

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png" style="width: 141px; height: 121px;" />
<pre>
输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png" style="width: 281px; height: 141px;" />
<pre>
输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
输出：false
解释：不存在由顶点 0 到顶点 5 的路径.
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 105</code></li>
	<li><code>0 &lt;= edges.length &lt;= 2 * 105</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ui, vi &lt;= n - 1</code></li>
	<li><code>ui != vi</code></li>
	<li><code>0 &lt;= source, destination &lt;= n - 1</code></li>
	<li>不存在重复边</li>
	<li>不存在指向顶点自身的边</li>
</ul>