🔗 🟢 1791. Find Center of Star Graph 1287

tags: `Weekly Contest 232` `圖(Graph)`

題意

有一個無向星形圖，包含 $n$ 個節點，分別編號從 $1$ 到 $n$ 。星形圖是一個圖，其中有一個中心節點，且有恰好 $n - 1$ 條邊將中心節點與其他所有節點連接。

給定一個二維整數陣列 $edges$ ，其中每個 $edges[i] = [u_i, v_i]$ 表示節點 $u_i$ 和 $v_i$ 之間有一條邊。返回給定星形圖的中心。

思路：統計度數(degree)

由於中心點和其他點相連的邊數為 $n - 1$ ，因此可以統計每個節點的度數，找出度數為 $n - 1$ 的節點即為中心點。

複雜度分析

時間複雜度： $\mathcal{O}(n)$
空間複雜度： $\mathcal{O}(n)$

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1
        deg = [0] * (n + 1)
        for u, v in edges:
            deg[u] += 1
            deg[v] += 1
        return deg.index(n - 1)

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<int> deg(n + 1, 0);
        for (auto e : edges) {
            int u = e[0], v = e[1];
            deg[u]++;
            deg[v]++;
        }
        for (int i = 1; i <= n; i++) {
            if (deg[i] == n - 1) return i;
        }
        return -1;
    }
};