shortest-cycle-in-a-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>. The edges in the graph are represented by a given 2D integer array <code>edges</code>, where <code>edges[i] = [ui, vi]</code> denotes an 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.

Return the length of the shortest cycle in the graph. If no cycle exists, return <code>-1</code>.

A cycle is a path that starts and ends at the same node, and each edge in the path is used only once.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/04/cropped.png" style="width: 387px; height: 331px;" />
<pre>
Input: n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
Output: 3
Explanation: The cycle with the smallest length is : 0 -&gt; 1 -&gt; 2 -&gt; 0 
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/04/croppedagin.png" style="width: 307px; height: 307px;" />
<pre>
Input: n = 4, edges = [[0,1],[0,2]]
Output: -1
Explanation: There are no cycles in this graph.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= edges.length &lt;= 1000</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ui, vi &lt; n</code></li>
	<li><code>ui != vi</code></li>
	<li>There are no repeated edges.</li>
</ul>

findShortestCycle

Shortest Cycle in a Graph

Redundant Connection

redundant-connection

冗余连接

Longest Cycle in a Graph

longest-cycle-in-a-graph

图中的最长环

Divide Nodes Into the Maximum Number of Groups

divide-nodes-into-the-maximum-number-of-groups

将节点分成尽可能多的组

Breadth-First Search

Graph

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

返回图中 最短 环的长度。如果不存在环，则返回 <code>-1</code> 。

环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/04/cropped.png" style="width: 387px; height: 331px;">
<pre>输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出：3
解释：长度最小的循环是：0 -&gt; 1 -&gt; 2 -&gt; 0 
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/04/croppedagin.png" style="width: 307px; height: 307px;">
<pre>输入：n = 4, edges = [[0,1],[0,2]]
输出：-1
解释：图中不存在循环
</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= edges.length &lt;= 1000</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ui, vi &lt; n</code></li>
	<li><code>ui != vi</code></li>
	<li>不存在重复的边</li>
</ul>