Find Center of Star Graph

I had this on a phone screen and watched the candidate jump straight to building an adjacency map and counting degrees. That works in O(n), but it misses the structural shortcut: in a star graph, the center is the vertex shared by EVERY edge. So just look at the first two edges. The four endpoints contain the center exactly twice; pick the duplicate. The catalog covers Graph Representation but skipped this constant-time observation.

Find Center of Star Graph

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] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. Return the center of the given star graph.

Examples

Example 1:

• Input: edges = [[1, 2], [2, 3], [4, 2]]
• Output: 2
• Explanation: Every edge involves vertex 2.

Example 2:

• Input: edges = [[1, 2], [5, 1], [1, 3], [1, 4]]
• Output: 1
• Explanation: Every edge involves vertex 1.

Example 3:

• Input: edges = [[1, 2], [1, 3]]
• Output: 1
• Explanation: First two edges are [1, 2] and [1, 3]. Their shared endpoint is 1, the center.

Example 4:

• Input: edges = [[7, 1], [1, 8]]
• Output: 1
• Explanation: Even with arbitrary labels, the shared endpoint of the first two edges is the center.

Constraints

• 3 <= n <= 10^5.
• edges.length == n - 1.
• edges[i].length == 2.
• 1 <= u_i, v_i <= n.
• u_i != v_i.
• The given edges represent a valid star graph.

Follow-up

Why does looking at only the first two edges suffice? In a star graph, the center is incident to ALL edges, including the first two. The non-center endpoints of edges 0 and 1 are different leaves (a leaf appears in exactly one edge). So the center is the unique vertex appearing in both edges[0] and edges[1].