[Leetcode]1791. Find Center of Star Graph

김지원·2022년 5월 18일
0

📄 Description

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]=[ui,vi]edges[i] = [{u_i}, {v_i}] indicates that there is an edge between the nodes ui{u_i} and vi{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.

Example 2:

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

Constraints:

  • 3<=n<=1053 <= n <= {10^5}
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= ui{u_i}, vi{v_i} <= n
  • ui{u_i} != vi{v_i}
  • The given edges represent a valid star graph.

💻 My Submission

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        _dict=defaultdict(list)
        for n1,n2 in edges:
            _dict[n1].append(n2)
            _dict[n2].append(n1)
        for k,v in _dict.items():
            if len(_dict[k])==len(edges):
                return k

References

profile
Make your lives Extraordinary!

0개의 댓글