* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)

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

[题目链接](https://leetcode.cn/problems/find-center-of-star-graph/)

本题思路就是统计各个节点的度（这里没有区别入度和出度），如果某个节点的度等于这个图边的数量。 那么这个节点一定是中心节点。 

什么是度，可以理解为，链接节点的边的数量。 题目中度如图所示： 

![1791.找出星型图的中心节点](https://file1.kamacoder.com/i/algo/20220704113207.png) 

至于出度和入度，那就是在有向图里的概念了，本题是无向图。

本题代码如下： 

```c++ 

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        unordered_map<int ,int> du;
        for (int i = 0; i < edges.size(); i++) { // 统计各个节点的度    
                du[edges[i][1]]++;
                du[edges[i][0]]++;
        }
        unordered_map<int, int>::iterator iter;  // 找出度等于边熟练的节点
        for (iter = du.begin(); iter != du.end(); iter++) { 
            if (iter->second == edges.size()) return iter->first;
        }
        return -1;
    }
};
```

其实可以只记录度不用最后统计，因为题目说了一定是星状图，所以 一旦有 节点的度 大于1，就返回该节点数值就行，只有中心节点的度会大于1。 

代码如下：

```c++ 
class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        vector<int> du(edges.size() + 2);  // edges.size() + 1 为节点数量，下标表示节点数，所以+2 
        for (int i = 0; i < edges.size(); i++) {
            du[edges[i][1]]++;
            du[edges[i][0]]++;
            if (du[edges[i][1]] > 1) return edges[i][1];
            if (du[edges[i][0]] > 1) return edges[i][0];

        }
        return -1;
    }
};
```

以上代码中没有使用 unordered_map，因为遍历的时候，开辟新空间会浪费时间，而采用 vector，这是 空间换时间的一种策略。 

代码其实可以再精简： 

```c++ 
class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        vector<int> du(edges.size() + 2);
        for (int i = 0; i < edges.size(); i++) {
            if (++du[edges[i][1]] > 1) return edges[i][1];
            if (++du[edges[i][0]] > 1) return edges[i][0];
        }
        return -1;
    }
};
```