EasyNo. 1791
Find Center of Star Graph — LeetCode 1791 Python Solution
- Pattern
- Depth-First Search
- Topics
- Graph
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
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.
Python solution
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
return edges[0][0] if edges[0][0] in edges[1] else edges[0][1]Complexity
- Time
- O(1)
- Space · auxiliary
- O(1)
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1791. Find Center of Star Graph is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0207 | Course Schedule | Medium |
| 0210 | Course Schedule II | Medium |
| 0310 | Minimum Height Trees | Medium |
| 0332 | Reconstruct Itinerary | Hard |
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
Frequently asked questions
- How hard is LeetCode 1791. Find Center of Star Graph?
LeetCode 1791. Find Center of Star Graph is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1791. Find Center of Star Graph?
The Python solution on this page runs in O(1).
- What is the space complexity of LeetCode 1791. Find Center of Star Graph?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1791. Find Center of Star Graph cover?
LeetCode 1791. Find Center of Star Graph is tagged Graph on LeetCode.