[LeetCode] Find Center of Star Graph

1.문제

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.

star graph가 주어지고 graph의 노드들을 연결하는 엣지에 대한 정보를 2차원 배열로 주어진다고 할 때 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 <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 1 <= ui, vi <= n
• ui != vi
• The given edges represent a valid star graph.

2.풀이

1. 특정 두 엣지를 선택했을 때 두 엣지에 공통으로 존재하는 노드가 center node이다.

/**
 * @param {number[][]} edges
 * @return {number}
 */
const findCenter = function (edges) {
  const firstEdge = edges[0];

  // 첫번째 엣지의 노드중 다음 엣지의 노드랑 중복되는 노드를 리턴한다
  return firstEdge.includes(edges[1][0]) ? edges[1][0] : edges[1][1];
};

3.결과