leetcode : Redundant Connection

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

Redundant Connection - LeetCode

 

내가 union find쪽으로 많이 부족한거같아서 연습을 좀 하려고 풀었다.

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        group = [i for i in range(1001)]
        
        def find(x):
            if group[x] != x:
                group[x] = find(group[x])
            return group[x]
        
        def union(i, j):
            if j > i:
                i,j = j,i
            
            gi = find(i)
            gj = find(j)
            
            if gi != gj: 
                group[gj] = gi
                return True
            else:
                return False
            
        for edge in edges:
            result = union(edge[0], edge[1])
            if not result:
                return edge
        
        return None

 

정말 간단하다.

그냥 edge를 이용해서 vertices를 순차적으로 union해가면서 이미 한 집합이라 union 실패하는 엣지를 찾으면 된다.