题目
有一个无向的 星型 图,由 n
个编号从 1
到 n
的节点组成。星型图有一个 中心 节点,并且恰有 n - 1
条边将中心节点与其他每个节点连接起来。
给你一个二维整数数组 edges
,其中 edges[i] = [ui, vi]
表示在节点 ui
和 vi
之间存在一条边。请你找出并返回 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 <= ui, vi <= n
ui != vi
- 题目数据给出的
edges
表示一个有效的星型图
解题
方法一:计数
思路
遍历 edges
中的每条边并计算每个节点的度,度为 n - 1
的节点即为中心节点。
代码
class Solution {
public int findCenter(int[][] edges) {
int n = edges.length;
int[] counts = new int[n + 2];
for (int[] edge : edges) {
if (++counts[edge[0]] == n) return edge[0];
if (++counts[edge[1]] == n) return edge[1];
}
return -1;
}
}
方法二:模拟
思路
根据题意,中心节点必然出现在所有的 edges[i]
中,因此使用前两条边即可确定答案。
起始让 edges[0][0]
和 edges[0][1]
作为答案候选,然后在 edges[1]
关系中检查哪个候选出现过。
代码
class Solution {
public int findCenter(int[][] edges) {
return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ?
edges[0][0] : edges[0][1];
}
}
评论区