1791. 找出星型圖的中心節(jié)點(diǎn)
難度簡單
有一個無向的 星型 圖学辱，由 n 個編號從 1 到 n 的節(jié)點(diǎn)組成乘瓤。星型圖有一個 中心 節(jié)點(diǎn)，并且恰有 n - 1 條邊將中心節(jié)點(diǎn)與其他每個節(jié)點(diǎn)連接起來策泣。
給你一個二維整數(shù)數(shù)組 edges 衙傀，其中 edges[i] = [u_i, v_i] 表示在節(jié)點(diǎn) u<_i 和 v_i 之間存在一條邊。請你找出并返回 edges 所表示星型圖的中心節(jié)點(diǎn)萨咕。
我的題解
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
dic = {}
for (i,j) in edges:
if i in dic:
return i
else:
dic[i] = 1
if j in dic:
return j
else:
dic[j] = 1
官方題解
方法一：計(jì)算每個節(jié)點(diǎn)的度
由 nn 個節(jié)點(diǎn)組成的星型圖中统抬，有一個中心節(jié)點(diǎn)，有 n - 1 條邊分別連接中心節(jié)點(diǎn)和其余的每個節(jié)點(diǎn)。因此聪建，中心節(jié)點(diǎn)的度是 n - 1钙畔，其余每個節(jié)點(diǎn)的度都是 1。一個節(jié)點(diǎn)的度的含義是與該節(jié)點(diǎn)相連的邊數(shù)妆偏。
遍歷 edges 中的每條邊并計(jì)算每個節(jié)點(diǎn)的度刃鳄，度為 n?1 的節(jié)點(diǎn)即為中心節(jié)點(diǎn)。
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/find-center-of-star-graph/solution/zhao-chu-xing-xing-tu-de-zhong-xin-jie-d-1xzm/
來源：力扣（LeetCode）
著作權(quán)歸作者所有钱骂。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)叔锐，非商業(yè)轉(zhuǎn)載請注明出處。
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
n = len(edges) + 1
degrees = [0] * (n + 1)
for x, y in edges:
degrees[x] += 1
degrees[y] += 1
for i, d in enumerate(degrees):
if d == n - 1:
return i
妙~方法二：尋找出現(xiàn)在兩條邊中的節(jié)點(diǎn)
由于只有星型圖的中心節(jié)點(diǎn)的度是 n - 1见秽，其余每個節(jié)點(diǎn)的度都是 1愉烙，因此只有星型圖在所有的邊中都出現(xiàn)，其余每個節(jié)點(diǎn)分別只在一條邊中出現(xiàn)解取。
根據(jù)星型圖的上述性質(zhì)可知步责，對于星型圖中的任意兩條邊，星型圖的中心節(jié)點(diǎn)一定同時在這兩條邊中出現(xiàn)禀苦，其余節(jié)點(diǎn)一定不會同時在這兩條邊中出現(xiàn)蔓肯。因此，可以任選兩條邊振乏，然后尋找這兩條邊的公共節(jié)點(diǎn)蔗包，該節(jié)點(diǎn)即為星型圖的中心節(jié)點(diǎn)。
具體做法是慧邮，選擇 edges[0][0] 和 edges[1] 這兩條邊调限，則星型圖的中心節(jié)點(diǎn)是edges[0][0] 或者edges[0][1]。如果edges[0][0] 和 [1]edges[1] 的兩個節(jié)點(diǎn)之一相同則 edges[0][0] 是星型圖的中心節(jié)點(diǎn)误澳，如果 edges[0][0] 和 edges[1] 的兩個節(jié)點(diǎn)都不相同則 edges[0][1] 是星型圖的中心節(jié)點(diǎn)耻矮。
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/find-center-of-star-graph/solution/zhao-chu-xing-xing-tu-de-zhong-xin-jie-d-1xzm/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)忆谓，非商業(yè)轉(zhuǎn)載請注明出處裆装。
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
return edges[0][0] if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1] else edges[0][1]
