describe

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] indicates that there is an edge between the nodes ui and vi. 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.
Copy the code

Example 2:

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

Note:

3 <= n <= 105 edges.length == n - 1 edges[i].length == 2 1 <= ui, vi <= n ui ! = vi The given edges represent a valid star graph.Copy the code

parsing

According to the meaning of the question, there must be a central point and n-1 edges. Due to various restrictions on the peripheral conditions, only the points that appear at least twice in the edges need to be found. Therefore, the points among edges are traversed and counted.

answer

class Solution(object):
    def findCenter(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: int
        """
        d = {}
        n = len(edges)
        for edge in edges:
            if edge[0] not in d:
                d[edge[0]] = 1
            else:
                d[edge[0]] += 1
            if d[edge[0]] == 2:
                return edge[0]
            
            if edge[1] not in d:
                d[edge[1]] = 1
            else:
                d[edge[1]] += 1
            if d[edge[1]] == 2:
                return edge[1]
            
        return -1
        	      
		
Copy the code

The results

Given in the linked list. Memory Usage: 10000 ms Given in Python online submissions for Find Center of Star Graph.Copy the code

Original link: leetcode.com/problems/fi…

Your support is my biggest motivation