【LeetCode】 1791. Find Center of Star Graph 解答・解説【Python】

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- グラフ理論

詳細

問題

原文

There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. Return the center of the given star graph.

Example 1:

Input: edges = [[1,2],[2,3],[4,2]] Output: 2 Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

1
2
3

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

Input: edges = [[1,2],[5,1],[1,3],[1,4]] Output: 1

1
2

Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

Constraints:

3 <= n <= 10⁵

edges.length == n - 1

edges[i].length == 2

1 <= u_i, v_i <= n

u_i != v_i

The given edges represent a valid star graph.

内容(和訳)

n個のノードがそれぞれ1からnまでのラベルづけされた無向スターグラフがあります。

スターグラフは1つ中央のノードとn-1個の中央ノードとだけつながる周辺ノードがあります。

2次元の整数配列edgesが与えられます。それぞれの要素edges[i]=[ui, vi]はノードuiとノードviの間に辺があることを示します。スターグラフの中央のノードを返してください。

※正しくない可能性があります。

解答

解答1：Python

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        dic = {}
        
        for i in range(1, len(edges)+2):
            dic[i] = 0

        for i,v in edges:
            dic[i] += 1
            dic[v] += 1
        
        print(dic)
        answer = 1
        for i in dic.keys():
            if dic[i] > answer:
                answer = i
                        
        return answer

class Solution:

def findCenter(self, edges: List[List[int]]) -> int:

dic = {}

for i in range(1, len(edges)+2):

dic[i] = 0

for i,v in edges:

dic[i] += 1

dic[v] += 1

print(dic)

answer = 1

for i in dic.keys():

if dic[i] > answer:

answer = i

return answer

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：56. Merge Intervals

次：

LeetCode 解答・解説記事一覧