Skip to main content

Uncategorized

A holding area for graph problems that don't yet belong to a named pattern section. As patterns emerge, these get promoted into their own sections.

1791. Find Center of Star Graph​

Easy·
3 Approachesclick to switch
Explanation

In a star graph, one center node is connected to every other node, and there are no other edges. The general approach: count how many edges touch each node, then return the node whose degree equals len(counter) - 1 (it is connected to all other nodes). Correct for any graph shape, but it does full O(E) work and builds a degree map.

Analysis
Time
O(V + E)
  • Every edge is scanned once to build counter - O(E).
  • The final pass over counter.items() checks every node once - O(V).
Space
O(V)
  • counter stores one degree entry per node - O(V).
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
counter = collections.defaultdict(int)
for a, b in edges:
counter[a] += 1
counter[b] += 1
for node, degree in counter.items():
if degree == len(counter) - 1:
return node