大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

找出星型图的中心顶点。中心顶点与其他每个顶点都相连。

解题方法

度

根据图论：「度」是一个顶点连接了几条边。

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

假设星型图的顶点数目为 N，那么中心顶点的度是 N - 1。

所以，我们可以求出每个顶点的度，如果某个顶点的度是 N - 1，那么就是中心顶点。

为什么本题我要采用「度」这个解法，而不是直接选取两条边，看两条边的交点呢？

因为我认为大部分题目都是在考察一个知识点的，而不是考你的直觉、技巧、奇思妙想、巧妙解法、找规律。

只有学会了题目背后的知识点，做题才能一通百通。

C++ 代码如下：

  1. class Solution {
  2. public:
  3.     int findCenter(vector<vector<int>>& edges) {
  4.         unordered_map<int, int> degree;
  5.         for (auto& edge : edges) {
  6.             degree[edge[0]] ++;
  7.             degree[edge[1]] ++;
  8.         }
  9.         int N = degree.size();
  10.         for (auto& v : degree) {
  11.             if (v.second == N - 1) {
  12.                 return v.first;
  13.             }
  14.         }
  15.         return -1;
  16.     }
  17. };

Python 代码如下：

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        counter = collections.Counter()
        for edge in edges:
            counter[edge[0]] += 1
            counter[edge[1]] += 1
        return counter.most_common(1)[0][0]


  • 时间复杂度：$O(N + E)$，其中 $N$ 是边数，$E$ 是顶点数，本题中 $E = N + 1$。
  • 空间复杂度：$O(E)$，$E$是顶点数。

总结

  1. 学会题目背后的知识，以不变应万变。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。