Find Center of Star Graph

easy graph

Problem

Given the edges of an undirected star graph, return its center node.

Inputedges = [[1,2],[2,3],[4,2]]

Output2

Node 2 appears in every edge.

edges (u,v;...)

def find_center(edges):
    a, b = edges[0]
    c, d = edges[1]
    return a if a == c or a == d else b

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

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

int findCenter(vector<vector<int>>& edges) {
    return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ? edges[0][0] : edges[0][1];
}

Explanation

In a star graph one central node touches every edge, while every other node touches exactly one. So the center must be the node that the first two edges have in common — and we only need to look at those two edges.

Take the endpoints of edges[0] as a, b and of edges[1] as c, d. If a also appears in the second edge (a == c or a == d), then a is the shared node and thus the center. Otherwise the shared node must be b.

This works because the center is guaranteed to be on both edges, while a leaf node sits on only one. Two edges are enough to pin down which endpoint is shared.

Example: edges = [[1,2],[2,3],[4,2]]. First edge is (1,2), second is (2,3). Is 1 in the second edge? No. So the center is the other endpoint, 2 — which indeed appears in every edge.

No loop or counting is needed, so the answer is found in constant time.

Time: O(1) Space: O(1)