找出星型图的中点

本文主要是介绍找出星型图的中点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题指路

找出星型图的中点

题目描述

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

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

解题思路

这道题有个十分关键的信息——只有中心点才会有$n-1$条与之关联的边，即整张图中只有一个点的度为$n-1$，且为最大。
所以，接下来其实就可以直接遍历整张图求每个点的度，然后输出度最大的点即可。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

然而，小丑竟是我自己，在比赛结束后，我看了题解才发现这道题是星状图，且只有一个中心点……所以直接输出前两个边中的公共点即可。

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

代码1

class Solution 
{public:int findCenter(vector<vector<int>>& edges) {int len = edges.size();int point[100001] = {0};int max = 0;for(int i = 0; i < len; i++){point[edges[i][0]]++;point[edges[i][1]]++;if(point[edges[i][0]] > point[max])max = edges[i][0];if(point[edges[i][1]] > point[max])max = edges[i][1];}return max;}
};

代码2

class Solution:def findCenter(self, edges: List[List[int]]) -> int:return edges[0][0] if edges[0][0] in edges[1] else edges[0][1]

这篇关于找出星型图的中点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---