[LeetCode] 1791. Find Center of Star Graph

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

leetcode - Find Center of Star Graph

문제 유형 : 그래프, 해시

문제 난이도 : Easy

 

문제

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.

 

방향이 없는 별 그래프가 있다. n개의 노드가 1부터 n까지 라벨링되어있고, 별 그래프는 하나의 중앙 노드에 다른 n-1개의 노드들이 각각 연결되어있는 것을 말한다.

간선의 정보다 2D 배열로 주어진다. edges[i] = [u_i, v_i]는 u_i부터 v_i까지의 간선이 있음을 나타낸다.

별그래프의 중앙을 반환하시오.

 

풀이

간선에 두 번 이상 나오는 노드가 중앙노드이다.

 

코드

C++

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        unordered_map<int, int> mp;
        for(const auto &edge : edges) {
            int a = edge[0];
            int b = edge[1];

            if(mp[a]) return a;
            if(mp[b]) return b;
            mp[a]++;
            mp[b]++;
        }
        return -1;
    }
};