Find Center of Star Graph
The center node appears in every edge — so it must appear in the first two edges.
2 min read
Problem#
A star graph on n nodes has one center connected to every other node. Given the edge list, return the center’s label.
Examples#
edges = [[1,2],[2,3],[4,2]]→2edges = [[1,2],[5,1],[1,3],[1,4]]→1
Constraints#
3 <= n <= 10^5,edges.length == n - 1.
Approach#
The center appears in every edge. Compare the two endpoints of the first edge against the two of the second; the common label is the center.
Solution#
class Solution {public: int findCenter(vector<vector<int>>& edges) { int a = edges[0][0], b = edges[0][1]; if (a == edges[1][0] || a == edges[1][1]) return a; return b; }};func findCenter(edges [][]int) int { a, b := edges[0][0], edges[0][1] if a == edges[1][0] || a == edges[1][1] { return a } return b}from typing import List
class Solution: def findCenter(self, edges: List[List[int]]) -> int: a, b = edges[0][0], edges[0][1] if a == edges[1][0] or a == edges[1][1]: return a return bfunction findCenter(edges) { const [a, b] = edges[0]; if (a === edges[1][0] || a === edges[1][1]) return a; return b;}class Solution { public int findCenter(int[][] edges) { int a = edges[0][0], b = edges[0][1]; if (a == edges[1][0] || a == edges[1][1]) return a; return b; }}function findCenter(edges: number[][]): number { const [a, b] = edges[0]; if (a === edges[1][0] || a === edges[1][1]) return a; return b;}Editorial#
A graph is a star iff exactly one node has degree n - 1 and all others have degree 1. Since the input is guaranteed to be a star, the first two edges already pin down the center via their shared endpoint.
Complexity#
- Time: O(1).
- Space: O(1).
Concept revision#
Related#