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

题目描述

这是 LeetCode 上的 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 表示一个有效的星型图

---

模拟

根据题意，中心节点必然出现在所有的 $edges[i]$ 中，因此使用前两条边即可确定答案。

起始让 $edges[0][0]$ 和 $edges[0][1]$ 作为答案候选，然后在 $edges[1]$ 关系中检查哪个候选出现过。

代码：

class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0], b = edges[0][1];
        if (a == edges[1][0] || a == edges[1][1]) return a;
        else return b;
    }
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

进阶

显然，如果将每个 $edges[i]$ 看做两点之间的「双向边」的话，那么星型图为「欧拉图」，所有点的出度均等于入度。

容易将题拓展为求欧拉回路的问题：

给定星与星之间的距离，从某个星的位置出发，经过所有的边（可重复经过）并回到起点的最短距离，输出能够取得最短距离的路径（无解输出 $-1$）。

答案就是求「欧拉回路」，其中「可重复经过边」包含了「可重复经过点」的含义。

由于星星图存在中心点，必然有解（但为了题目描述的完整性，出题都会预设一个无解返回值）；同时也不会重复经过某条边（仍然是为了题目描述完整性才这样写）。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1791 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。