【LeetCode每日一题】——1791.找出星型图的中心节点

一【题目类别】

• 图

二【题目难度】

• 简单

三【题目编号】

• 1791.找出星型图的中心节点

四【题目描述】

• 有一个无向的 星型 图，由 $n$ 个编号从 $1$ 到 $n$ 的节点组成。星型图有一个 中心 节点，并且恰有 $n-1$ 条边将中心节点与其他每个节点连接起来。
• 给你一个二维整数数组 $edges$ ，其中 $edges[i]=[u_i,v_i]$ 表示在节点 $u_i$ 和 $v_i$ 之间存在一条边。请你找出并返回 $edges$ 所表示星型图的中心节点。

五【题目示例】

• 示例 1：
  

  • 输入：edges = [[1,2],[2,3],[4,2]]
  • 输出：2
  • 解释：如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。

• 示例 2：

  • 输入：edges = [[1,2],[5,1],[1,3],[1,4]]
  • 输出：1

六【题目提示】

• $3<=n<=10^5$
• $edges.length==n-1$
• $edges[i].length==2$
• $1<=u_i,v_i<=n$
• $u_i!=v_i$
• 题目数据给出的 $edges$ 表示一个有效的星型图

七【解题思路】

• 该题需要利用图的基本性质，即度的概念
• 根据题意，“星型图”的中心节点连接其余n - 1个节点
• 所以“星型图”的中心节点的度为n - 1
• 故只需要计算每个节点的度，度为n - 1的节点即为“星型图”的中心节点
• 具体细节可以参考下面的代码
• 最后返回结果即可

八【时空频度】

• 时间复杂度：$O(n)$，$n$为图中的节点数量
• 空间复杂度：$O(n)$，$n$为图中的节点数量

九【代码实现】

1. Java语言版

class Solution {public int findCenter(int[][] edges) {// 获取节点数量int n = edges.length + 1;// 初始化数组，表示图中节点的度int[] degrees = new int[n + 1];// 计算图中每个节点的度for (int i = 0; i < edges.length; i++) {degrees[edges[i][0]]++;degrees[edges[i][1]]++;}// 若某个节点的度=节点数量-1，其即为星型图的中心节点for (int i = 1; i < degrees.length; i++) {if (degrees[i] == n - 1) {return i;}}return -1;}
}

2. Python语言版

class Solution:def findCenter(self, edges: List[List[int]]) -> int:# 获取节点数量n = len(edges) + 1# 初始化数组，表示图中节点的度degrees = [0] * (n + 1)# 计算图中每个节点的度for x, y in edges:degrees[x] += 1degrees[y] += 1# 若某个节点的度=节点数量-1，其即为星型图的中心节点for index, degree in enumerate(degrees):if degree == n - 1:return index

3. C语言版

int findCenter(int** edges, int edgesSize, int* edgesColSize)
{// 获取节点数量int n = edgesSize + 1;// 初始化数组，表示图中节点的度int* degrees = (int*)malloc(sizeof(int) * (n + 1));memset(degrees, 0, (n + 1) * sizeof(int));// 计算图中每个节点的度for (int i = 0; i < edgesSize; i++){degrees[edges[i][0]]++;degrees[edges[i][1]]++;}// 若某个节点的度=节点数量-1，其即为星型图的中心节点for (int i = 0; i < (n + 1); i++){if (degrees[i] == (n - 1)){return i;}}return -1;
}

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C语言版