156일 (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] = [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 <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 1 <= ui, vi <= n
• ui != vi
• The given edges represent a valid star graph.

 

- 접근방법

 

별 모양 그래프의 중앙 노드의 값을 찾으라는 문제이다.

 

- 정석적으로 본다면 edge가 3개일때 vertex는 4개가 되고 vertex 1~4 중 edge에 중복되어 나온 노드를 리턴하면 된다.

- 더 간단하게 본다면 2번이상 나온 vertex를 리턴하면 된다.

→ 중앙노드는 자신을 제외한 모든 노드와 연결되어있고, 중앙노드를 제외한 모든 노드들은 중앙노드랑만 연결되어있다.

따라서 edges를 순회하며 2번이상 나온 vertex가 중앙노드가 된다.

 

- 코드

class Solution {
    public int findCenter(int[][] edges) {
        Set<Integer> set = new HashSet<>();

        for(int[] edge : edges) {
            if(set.contains(edge[0])) return edge[0];
            else if(set.contains(edge[1])) return edge[1];
            set.add(edge[0]);
            set.add(edge[1]);
        }


        return -1;
    }
}

 

Set 자료구조를 이용하여 중복된 노드를 리턴하였다.

이제부터 연결리스트 관련 문제는 그만 풀고 그래프에 도전해봐야겠다.

 

 

 

 

https://leetcode.com/problems/find-center-of-star-graph/

Find Center of Star Graph - LeetCode