find-center-of-star-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 an undirected star graph consisting of <code>n</code> nodes labeled from <code>1</code> to <code>n</code>. A star graph is a graph where there is one center node and exactly <code>n - 1</code> edges that connect the center node with every other node.

You are given a 2D integer array <code>edges</code> where each <code>edges[i] = [ui, vi]</code> indicates that there is an edge between the nodes <code>ui</code> and <code>vi</code>. Return the center of the given star graph.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/24/star_graph.png" style="width: 331px; height: 321px;" />
<pre>
Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.
</pre>

Example 2:

<pre>
Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= ui, vi &lt;= n</code></li>
	<li><code>ui != vi</code></li>
	<li>The given <code>edges</code> represent a valid star graph.</li>
</ul>

findCenter

Find Center of Star Graph

Maximum Star Sum of a Graph

maximum-star-sum-of-a-graph

图中最大星和

Graph

有一个无向的 星型 图，由 <code>n</code> 个编号从 <code>1</code> 到 <code>n</code> 的节点组成。星型图有一个 中心 节点，并且恰有 <code>n - 1</code> 条边将中心节点与其他每个节点连接起来。

给你一个二维整数数组 <code>edges</code> ，其中 <code>edges[i] = [ui, vi]</code> 表示在节点 <code>ui</code> 和 <code>vi</code> 之间存在一条边。请你找出并返回 <code>edges</code> 所表示星型图的中心节点。

 

示例 1：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/14/star_graph.png" style="width: 331px; height: 321px;" />
<pre>
输入：edges = [[1,2],[2,3],[4,2]]
输出：2
解释：如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。
</pre>

示例 2：

<pre>
输入：edges = [[1,2],[5,1],[1,3],[1,4]]
输出：1
</pre>

 

提示：

<ul>
	<li><code>3 <= n <= 105</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 <= ui, vi <= n</code></li>
	<li><code>ui != vi</code></li>
	<li>题目数据给出的 <code>edges</code> 表示一个有效的星型图</li>
</ul>