标签: 图
难度: Easy
有一个无向的 星型 图，由 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 <= 105edges.length == n - 1edges[i].length == 21 <= ui, vi <= nui != viedges 表示一个有效的星型图运行时间: 48 ms
内存: 39.6 MB
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
if(edges[0][0]==edges[1][0] or edges[0][0]==edges[1][1]):
return edges[0][0]
else:
return edges[0][1]
此题解利用了星型图的特性：中心节点会与其他所有节点都有连接。因此，只需要检查图中的前两条边就足够确定中心节点。如果第一条边的任一节点与第二条边的任一节点相同，那么这个相同的节点就是中心节点。这种方法非常高效，因为它不需要检查所有的边，只需比较前两条边。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
# 检查第一个和第二个边的端点是否有相同的，有则该节点为中心
if(edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1]):
return edges[0][0]
else:
return edges[0][1]
在星型图中，中心节点必须与所有其他节点相连。因此，任意两条边都至少有一个共同的节点，即为中心节点。比较第一条和第二条边的端点，必定会发现中心节点，因为中心节点是唯一连接多个节点的节点。这种方法利用了星型图的结构特性，简化了问题求解过程。
在星型图中，理论上这种情况不可能发生，因为所有非中心的节点只会与中心节点相连，不会直接相连。如果实际输入的数据出现了这种情况，那么这不符合星型图的定义，输入数据可能是错误的或者不是星型图。
此算法假设输入的图是一个标准的星型图，其中所有的节点至少与一个中心节点相连，不存在孤立节点。算法没有额外验证节点的合法性或检查是否有额外的边，它基于输入是有效的星型图的前提下进行操作。
如果输入的图不是一个标准的星型图，算法的输出可能是错误的。该算法只是简单地查找两条边共有的节点作为中心节点，如果图中存在环或其他结构，这种方法可能会错误地识别一个非中心节点为中心节点。因此，算法的准确性完全依赖于输入数据的正确性和对问题描述的遵守。