union-find 알고리즘

union find 자료구조

각각의 독립되어 있는 data를 그룹화 시켜 자료들을 관리할때 사용하는 자료구조

union

2개 원소로 이루어진 집합을 하나의 집합으로 합치기

find

특정 원소가 속한 집합이 뭔지 알려주는 연산

-> 서로소 집합 자료구조는 union + find 연산으로 구성되므로 union-find 자료구조라고 불리기도 함

연결이 되어있는지 안되어있는지 알아보는 알고리즘

# Union-find 알고리즘

arr=[0]*200

def findboss(member): # find 알고리즘
    global arr
    if arr[ord(member)]==0: # 매개변수에 해당하는 곳의 값이 0이라면
        return member       # 자기 자신이 보스!!
    ret=findboss(arr[ord(member)]) # else: 배열에 적혀있는 값으로 다시 보스 찾아보기
    return ret

def union(a,b): # union 알고리즘
    global arr
    aboss=findboss(a)  # boss 찾기
    bboss=findboss(b)
    if aboss==bboss:  # boss가 같다 -> 이미 같은 그룹
        return
    arr[ord(bboss)]=aboss  # 두보스가 다르다면 b의 보스에 해당하는 값에 a의 보스적기


union('A','B') # 두 그룹을 하나의 그룹으로
union('D','E') # 합쳐주는 함수
union('B','E')
union('B','D')
union('F','E')

y,x=input().split()
if findboss(y)==findboss(x): # boss 가 같다면 union 하다.
    print("같은그룹")
else: print("다른그룹")`

Union-find를 이용해서 cycle 탐색해보기

n=int(input())
edge=[]
for _ in range(n):
    edge.append(input().split())

arr=[0]*200

def findboss(member):
    global arr
    if arr[ord(member)]==0:
        return member
    ret=findboss(arr[ord(member)])
    arr[ord(member)]=ret
    return ret


# union 함수
def union(a,b):
    global arr

    fa,fb=findboss(a),findboss(b)
    if fa==fb:return 1
    arr[ord(fb)]=fa

answer=0
for i in range(n):
    a,b=edge[i]
    ret=union(a,b)
    if ret==1:
        answer=1
        break
if answer:print("cycle 발견")
else: print("cyccle 미발견")