algoadvance

1791 - 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.

Example:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2

Clarifying Questions

  1. Input Size Limits: What are the constraints on the number of nodes (n) and edges (edges)?
    • The graph will have n nodes and n-1 edges. Constraints: 3 <= n <= 10^5.
  2. Unique Star Graph: Will the input always represent a valid star graph?
    • Yes, the input will always represent a valid star graph.
  3. Node Labels: Are node labels always positive integers starting from 1?
    • Yes, nodes are labeled from 1 to n.

Strategy

To find the center of the star graph, observe that the center node will appear in every edge. Hence, it must be connected to n-1 other nodes. Given that the star graph always has exactly n-1 edges, the center node will show up most frequently in the edges list.

We can solve this in a very straightforward manner:

  1. Examine the first two edges. Since the center node must appear in all edges of the star graph, it must appear in the intersection of these edges.
  2. Return the common node between the first two edges as the center.

Code

Here is the solution to find the center of the star graph:

def findCenter(edges):
    # Grabbing the nodes from the first two edges
    u1, v1 = edges[0]
    u2, v2 = edges[1]

    # The center will be the common node between these two edges
    if u1 == u2 or u1 == v2:
        return u1
    else:
        return v1

# Example Test Case
edges = [[1,2], [2,3], [4,2]]
print(findCenter(edges))  # Output: 2

Time Complexity

This approach ensures efficient and clear identification of the center node in the star graph.

Try our interview co-pilot at AlgoAdvance.com