리트코드 684 Redundant Connection (파이썬)

https://leetcode.com/problems/redundant-connection/

Redundant Connection - LeetCode

 

---

아이디어

• 엣지의 정보가 주어지므로 엣지를 순차적으로 순회하며 연결시켜 그래프를 만든다.
• 그래프를 만들며 싸이클이 생기는 엣지의 정보를 발견하면 그 엣지를 return한다.

 

---

풀이 및 해설(주석)

class Solution(object):
    def findRedundantConnection(self, edges):

        n = len(edges)
        # 부모 초기화
        par = [i for i in range(n + 1)]

        def find(n):
            while par[n] != n:
                n = par[n]
            return n
        # n1과 n2의 부모가 같다면 합치지 않고 False를 return (부모가 같은 노드를 합치면 싸이클이 형성된다)
        def union(n1, n2):
            p1, p2 = find(n1), find(n2)
            if p1 == p2:
                return False
            par[p2] = p1
            return True

        # 부모가 같은 노드를 발견 == 싸이클이 되므로 False가 return됨
        for a, b in edges:
            if not union(a, b):
                return [a, b]