-
Notifications
You must be signed in to change notification settings - Fork 27
/
Copy path1791.FindCenterofStarGraph.py
47 lines (41 loc) · 1.47 KB
/
1791.FindCenterofStarGraph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
'''
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:
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:
Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1
Constraints:
- 3 <= n <= 10^5
- edges.length == n - 1
- edges[i].length == 2
- 1 <= ui, vi <= n
- ui != vi
- The given edges represent a valid star graph.
'''
#Difficulty: Medium
#60 / 60 test cases passed.
#Runtime: 836 ms
#Memory Usage: 50.7 MB
#Runtime: 836 ms, faster than 56.70% of Python3 online submissions for Find Center of Star Graph.
#Memory Usage: 50.7 MB, less than 16.71% of Python3 online submissions for Find Center of Star Graph.
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
count = {}
for edge in edges:
for val in edge:
if val not in count:
count[val] = 0
count[val] += 1
return max(count, key=count.get)