{x}
blog image

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

 

Example 1:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

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

 

Constraints:

  • 3 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • The given edges represent a valid star graph.

Solution Explanation for Finding the Center of a Star Graph

This problem asks to find the central node in a star graph given its edges. A star graph has one central node connected to all other nodes. The solution leverages the inherent property of a star graph to efficiently identify the center.

Approach: Exploiting the Graph Structure

The key observation is that the center node will be present in all edge pairs. Therefore, we can simply examine the first two edges provided. The node that appears in both edge pairs is the center.

Algorithm

  1. Access the First Two Edges: Retrieve the first two edge pairs from the input edges array.
  2. Check for Common Nodes: Compare the nodes in the first edge pair with the nodes in the second edge pair. If a node from the first pair is found in the second pair, that node is the center.
  3. Return the Center: Return the common node as the center of the star graph.

Time and Space Complexity Analysis

  • Time Complexity: O(1). The algorithm performs a constant number of comparisons, independent of the size of the graph.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space to store variables. It does not scale with the input size.

Code Implementation (Python)

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        """
        Finds the center node of a star graph.
 
        Args:
            edges: A list of lists, where each inner list represents an edge 
                   connecting two nodes.
 
        Returns:
            The ID of the center node.
        """
        a, b = edges[0]  # Extract nodes from the first edge
        c, d = edges[1]  # Extract nodes from the second edge
 
        # Check if 'a' is in the second edge; if so, it's the center
        if a == c or a == d:
            return a
        # Otherwise, 'b' must be the center
        else:
            return b

Code Implementation (Other Languages)

The same approach applies across various programming languages with minor syntax differences. The code snippets below showcase the algorithm's implementation in Java, C++, Go, TypeScript, Rust, and JavaScript. They all maintain the O(1) time and space complexity.

Java:

class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0], b = edges[0][1];
        int c = edges[1][0], d = edges[1][1];
        return a == c || a == d ? a : b;
    }
}

C++:

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int a = edges[0][0], b = edges[0][1];
        int c = edges[1][0], d = edges[1][1];
        return (a == c || a == d) ? a : b;
    }
};

Go:

func findCenter(edges [][]int) int {
	a, b := edges[0][0], edges[0][1]
	c, d := edges[1][0], edges[1][1]
	if a == c || a == d {
		return a
	}
	return b
}

TypeScript:

function findCenter(edges: number[][]): number {
    const [a, b] = edges[0];
    const [c, d] = edges[1];
    return (a === c || a === d) ? a : b;
};

Rust:

impl Solution {
    pub fn find_center(edges: Vec<Vec<i32>>) -> i32 {
        let (a, b) = (edges[0][0], edges[0][1]);
        let (c, d) = (edges[1][0], edges[1][1]);
        if a == c || a == d {
            a
        } else {
            b
        }
    }
}

JavaScript:

/**
 * @param {number[][]} edges
 * @return {number}
 */
var findCenter = function(edges) {
    const [a, b] = edges[0];
    const [c, d] = edges[1];
    return (a === c || a === d) ? a : b;
};

This efficient solution directly addresses the problem's constraints and provides a clear, concise, and optimally performant way to find the center node of a star graph.