99클럽 코테 스터디 24일차 TIL - 그래프

문제

Find Center of Star Graph

풀이

• 중심에 있는 노드를 찾는 것
• 중심 노드는 모든 노드들과 간선이 존재한다.
• 연결리스트를 만들어서 for문 순회하면서 모든 노드들과 간선이 존재하는 즉, edges.length와 동일한 노드를 찾는다.

코드

class Solution {
    public int findCenter(int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] graph = new ArrayList[n+1];
        
        for(int i = 1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        for(int[] edge: edges){
            int s = edge[0];
            int e = edge[1];
            graph[s].add(e);
            graph[e].add(s);
        }
        
        for(int i = 1; i <= n; i++) {
            if(graph[i].size() == edges.length) return i;
        }
        
        return -1;
    }
}

정리