[LeetCode] 684. Redundant Connection

😎풀이

1. edges를 통해 Map객체를 사용한 graph 생성
2. 문제 조건에 따라 edges 기준 후순위부터 순회
   2-1. 순환 관계를 갖는 요소라면 그대로 반환

function findRedundantConnection(edges: number[][]): number[] {
    const graph = new Map<number, number[]>()
    for(const [from, to] of edges) {
        graph.set(from, [...(graph.get(from) ?? []), to])
        graph.set(to, [...(graph.get(to) ?? []), from])
    }
    for(let i = edges.length - 1; i >= 0; i--) {
        const [from, to] = edges[i]
        const queue = [to]
        const visited = new Set<number>()
        visited.add(to)
        while(queue.length) {
            const node = queue.shift()
            const neighbors = graph.get(node) ?? []
            for(const neighbor of neighbors) {
                if((node === from && neighbor === to) || (node === to && neighbor === from)) continue
                if(neighbor === from) return [from, to]
                if(!visited.has(neighbor)) {
                    visited.add(neighbor)
                    queue.push(neighbor)
                }
            }
        }
    }
    return []
};