add-edges-to-make-degrees-of-all-nodes-even

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 an undirected graph consisting of <code>n</code> nodes numbered from <code>1</code> to <code>n</code>. You are given the integer <code>n</code> and a 2D array <code>edges</code> where <code>edges[i] = [ai, bi]</code> indicates that there is an edge between nodes <code>ai</code> and <code>bi</code>. The graph can be disconnected.

You can add at most two additional edges (possibly none) to this graph so that there are no repeated edges and no self-loops.

Return <code>true</code> if it is possible to make the degree of each node in the graph even, otherwise return <code>false</code>.

The degree of a node is the number of edges connected to it.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/agraphdrawio.png" style="width: 500px; height: 190px;" />
<pre>
Input: n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
Output: true
Explanation: The above diagram shows a valid way of adding an edge.
Every node in the resulting graph is connected to an even number of edges.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/aagraphdrawio.png" style="width: 400px; height: 120px;" />
<pre>
Input: n = 4, edges = [[1,2],[3,4]]
Output: true
Explanation: The above diagram shows a valid way of adding two edges.</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/aaagraphdrawio.png" style="width: 150px; height: 158px;" />
<pre>
Input: n = 4, edges = [[1,2],[1,3],[1,4]]
Output: false
Explanation: It is not possible to obtain a valid graph with adding at most 2 edges.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>2 &lt;= edges.length &lt;= 105</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= ai, bi &lt;= n</code></li>
	<li><code>ai != bi</code></li>
	<li>There are no repeated edges.</li>
</ul>

isPossible

Add Edges to Make Degrees of All Nodes Even

Minimum Degree of a Connected Trio in a Graph

minimum-degree-of-a-connected-trio-in-a-graph

一个图中连通三元组的最小度数

Graph

Hash Table

给你一个有 <code>n</code>&nbsp;个节点的 无向&nbsp;图，节点编号为&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;。再给你整数&nbsp;<code>n</code>&nbsp;和一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [ai, bi]</code>&nbsp;表示节点&nbsp;<code>ai</code> 和&nbsp;<code>bi</code>&nbsp;之间有一条边。图不一定连通。

你可以给图中添加 至多&nbsp;两条额外的边（也可以一条边都不添加），使得图中没有重边也没有自环。

如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回&nbsp;<code>true</code>&nbsp;，否则返回&nbsp;<code>false</code>&nbsp;。

点的度数是连接一个点的边的数目。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/agraphdrawio.png" style="width: 500px; height: 190px;" />

<pre>
输入：n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
输出：true
解释：上图展示了添加一条边的合法方案。
最终图中每个节点都连接偶数条边。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/aagraphdrawio.png" style="width: 400px; height: 120px;" />

<pre>
输入：n = 4, edges = [[1,2],[3,4]]
输出：true
解释：上图展示了添加两条边的合法方案。</pre>

示例 3：

<img alt="" src="https://assets.leetcode.com/uploads/2022/10/26/aaagraphdrawio.png" style="width: 150px; height: 158px;" />

<pre>
输入：n = 4, edges = [[1,2],[1,3],[1,4]]
输出：false
解释：无法添加至多 2 条边得到一个符合要求的图。</pre>

&nbsp;

提示：

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>2 &lt;= edges.length &lt;= 105</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= ai, bi &lt;= n</code></li>
	<li><code>ai != bi</code></li>
	<li>图中不会有重边</li>
</ul>