Problem Statement

Given a star graph, the task is to find its center, i.e., the vertex that minimizes the maximum distance to all other vertices in the graph.

Constraints:

• 3 <= n <= 105
  • This constraint defines the range of the number of vertices (n) in the graph. It states that the numbers of vertices in the graph must be at least 3 and at most 10^5 (100,000).
• edges.length == n - 1
  • This contains ensures that the number of edges in the graph is exactly (n-1). In a star graph with n vertices, there are n-1 edges because each leaf vertex is connected to the central vertex. This constraint ensures that the given edges represent a valid star graph.
• edges[i].length == 2
  • This constraint specifies that each edge in the graph is represented by an array of length 2.
• 1 <= ui, vi <= n
• ui != vi
  • This constraint ensures that the endpoints of each edge are distinct. It means that no edge connects a vertex to itself.
• The given edges represent a valid star graph.

Understanding

A star graph is a special type of graph where all vertices are connected to a single central vertex, forming a star-like structure. In an undirected star graph, each leaf vertex is connected directly to the central vertex.

Examples

Example 1:

    1
   / \
  2   3

In this example, vertex 1 is the center of the star graph.

Example 2:

     3
     |
     1
   /   \
  2     4

In this example, vertex 1 is still the center of the star graph.

Different Approaches

1 Using Vector

2 Constant Time

Intuition:

In a Star graph, for any two edges there will be one vertex as common which is the center of the graph.

Approach:

So, consider any two edges and check for the common vertex.

Thinking simply if the center node is there ,then it will be present in the first and second edge(vector) given in the edges vector.
So we check if the first element of the first edge is present in the second edge also, it will be the center, otherwise the second element will be the center.

Code Implementation: