8. 기타 그래프 이론: 서로소 집합 자료구조 union, find

union,find

 

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()) #노드개수v,간선개수e
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개의 간선이 있다

간선의 정보를 입력받고

연결된 노드 덩어리: 집합을 알아낸다

 

부모 노드를 저장할 리스트 parent가 필요하고(초기 parent의 값은 자기자신임)

간선정보 a,b를 받고

a의 부모,b의 부모를 비교한 후 값이 더 작은 부모로 통일시킴