Solution: Find Center of Star Graph

Statement

Given an array edges where each element edges[i] = [ui, vi] represents an edge between nodes ui and vi in an undirected star graph,A star graph is a graph where one central node is connected to every other node. If there are n nodes, then the central node must be connected to all other n-1 nodes. find the central node of this star graph.

Note: A star graph is a graph where one central node is connected to every other node. This implies that a star graph with n nodes has exactly n - 1 edges.

Constraints:

• $3 \leq$ n $\leq 10^3$

• edges.length $==$ n - 1

• edges[i].length $== 2$

• $1 \leq$ ui, vi $\leq$ n

• ui $\neq$ vi

• The given edges represent a valid star graph.

Solution

One of the first solutions that comes to our mind is to count the degreeThe degree of a node in a graph refers to the number of edges connected to that node. For an undirected graph, the degree of a node is simply the count of edges attached to it. of each node. In a star graph, the center node has the highest degree, equal to the number of nodes minus one, because it is connected to all other nodes. All other nodes have a degree of exactly $1$. By counting the degree of each node across all edges, we could identify the center as the node with the highest degree. This approach would work but requires traversing all the edges and counting the degree for each node, which results in a time complexity of $O(n)$.