[알고리즘 개념] 유니온-파인드 알고리즘

서로소 집합 자료구조

: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

종류

• 합집합(Union) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• 찾기(Find) : 특정한 원소가 집합이 어떤 집합인지 알려주는 연산

1. 합집합 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인
2. 모든 합집합 연산을 처리할 때까지 1번의 과정을 반복

def find_parent(parent,x):
    if parent[x]!=x:
        return find_parent(parent,parent[x])
    return x

def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
v,e = map(int,input().split())
parent = [0]*(v+1)

for i in range(1,v+1):
    parent[i]=i
    
for i in range(e):
    a,b= map(int,input().split())
    union_parent(parent,a,b)
    
print('각 원소가 속한 집합: ', end= ' ')
for i in range(1,v+1):
    print(find_parent(parent,i), end = ' ')
    
print()

print('부모 테이블: ',end='')
for i in range(1,v+1):
    print(parent[i],end=' ')

경로 압축

def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
v,e = map(int,input().split())
parent = [0]*(v+1)

for i in range(1,v+1):
    parent[i]=i
    
for i in range(e):
    a,b,=map(int,input().split())
    union_parent(parent,a,b)
    
print('각 원소가 속한 집합 : ',end='')
for i in range(1,v+1):
    print(find_parent(parent,i),end= ' ')
    
print()

print('부모 테이블: ',end="")
for i in range(1,v+1):
    print(parent[i],end=' ')

서로소 집합을 활용한 사이클 판별

v,e = map(int,input().split())
parent = [0]*(v+1)

for i in range(1,v+1):
    parent[i]=i
    
cycle = False

for i in range(e):
    a,b= map(int,input().split())
    if find_parent(parent,a)==find_parent(parent,b):
        cycle = True
        break
    else:
        union_parent(parent,a,b)
if cycle:
    print("사이클이 발생했습니다.")
    
else:
    print("사이클이 발생하지 않았습니다.")